Ścieżka hamiltona w grafie

[kylercopeland]

Czy prawdziwe jest stwierdzenie, że każdy graf G rzędu n w którym δ\(\displaystyle{ (G)>= \frac{n}{2} −- 1}\) posiada ścieżkę Hamiltona? Odpowiedź uzasadnij.

[Mruczek]

Dla \(\displaystyle{ n = 2}\) mamy minimalny stopień \(\displaystyle{ \delta(G) \ge \frac{2}{2} - 1 = 0}\). Bierzemy dwa wierzchołki izolowane, ten graf nie ma ścieżki Hamiltona.