Twierdzenie
Niech \(\displaystyle{ G}\) będzie spójnym grafem nie będącym drzewem. Wykazać, że jeśli dla każdego cyklu \(\displaystyle{ C}\) grafu \(\displaystyle{ G}\) i dla każdego wierzchołka \(\displaystyle{ v \in V(G) \setminus V(C)}\) istnieje więcej niż \(\displaystyle{ \frac{|C|}{2}}\) krawędzi z \(\displaystyle{ v}\) do \(\displaystyle{ V(C)}\), to \(\displaystyle{ G}\) jest grafem Hamiltona.
Dowód:
Przypuśćmy, że \(\displaystyle{ G}\) nie ma cyklu Hamiltona. Oznaczmy przez \(\displaystyle{ C_k}\) najdłuższy cykl w \(\displaystyle{ G}\) (a istnieje w tym grafie co najmniej jeden cykl, bo graf jest spójny i nie jest drzewem).
\(\displaystyle{ C_k}\) z założenia nie jest cyklem Hamiltona, a więc zbiór \(\displaystyle{ V(G) \setminus V(C)}\) nie jest pusty, czyli zawiera jakieś wierzchołki, np. \(\displaystyle{ x}\).
Z zasady szufladkowej Dirichleta możemy stwierdzić, że \(\displaystyle{ x}\) sąsiaduje z dwoma takimi wierzchołkami \(\displaystyle{ w, u \in V(C_k)}\), że \(\displaystyle{ w}\) i \(\displaystyle{ u}\) są połączone krawędzią (bo w \(\displaystyle{ C_k}\) jest dokładnie \(\displaystyle{ |V(C_k)|}\) wierzchołków, a \(\displaystyle{ x}\) łączy się z ponad połową z nich, więc któreś dwa w cyklu muszą być kolejne i zarazem sąsiadować z \(\displaystyle{ x}\)).
To znaczy, że cykl \(\displaystyle{ C_k}\) możemy przedłużyć o \(\displaystyle{ x}\), a cykl \(\displaystyle{ C_k\cup \left \{ x \right \}}\) jest dłuższy niż \(\displaystyle{ C_k}\), co przeczy definicji \(\displaystyle{ C_k}\) jako najdłuższego cyklu w \(\displaystyle{ G}\). Tak więc nasze przypuszczenie, że \(\displaystyle{ G}\) nie ma cyklu Hamiltona musiało być fałszywe.
\(\displaystyle{ \square}\)
Czy ten dowód jest poprawny? Wcześniej próbowałem najpierw udowodnić, że każdy wierzchołek z G jest w jakimś cyklu, ale nie bardzo wiedziałem jak to bardziej ruszyć. Przed chwilą wpadłem na ten pomysł i mi się wydaje, że jest OK, ale z doświadczenia wiem, że to co mi się wydaje, a to co jest, to dwie różne sprawy.