Matematyka.pl

Witam,

Mam takie zadanko

Korzystając z twierdzenia Diraca uzasadnij, że jeżeli G ma przynajmniej 2 wierzchołki i \(\displaystyle{ \delta(G)\ge\frac{V(G)-1}{2}}\) to G ma ścieżkę Hamiltona.

Znam twierdzenie Diraca i z tego co wiem tyczy się one cykli Hamiltona, a nie ścieżki. Trochę nie za bardzo wiem jak z niego skorzystać tym bardziej, że mamy tu do czynienia z 2 wierzchołkami, a twierdzenie Diraca można zastosować gdy mamy do czynienia z 3.

No dobra, to zauważ, że jeśli wezmę graf, który ma cykl Hamiltona i wyrzucę z tego grafu jeden wierzchołek, to dostanę graf, który ma ścieżkę Hamiltona, prawda?