Witam.
Nie wiem jak rozwiązać to zadanie:
"Niech \(\displaystyle{ G}\) będzie spójnym grafem, który nie jest drzewem. Niech dla każdego cyklu \(\displaystyle{ C}\) w grafie \(\displaystyle{ G}\) istnieje wierzchołek \(\displaystyle{ v \in V (G)-V (C)}\), który jest połączony krawędzią z więcej niż \(\displaystyle{ \frac{\left|V (C) \right| }{2}}\) wierzchołkami cyklu \(\displaystyle{ C}\). Wykazać, że graf \(\displaystyle{ G}\) ma cykl Hamiltona."
Nie wiem jak to ugryźć. Znam twierdzenia Orego i Diraca. Podejrzewam, że można to jakoś zrobić indukcyjnie, ale nie mam pomysłu jak. Narysowałem kilka grafów i wyszło mi, że jest spełnione twierdzenie Diraca, ale nie wiem jak to udowodnić.
Fray