Matematyka.pl

Witam, mam takie zadanie do rozwiązania:

Wykazać, że jeżeli \(\displaystyle{ G}\) jest niezorientowanym grafem regularnym stopnia \(\displaystyle{ d}\) o \(\displaystyle{ n=2d-1}\) wierzchołkach, to \(\displaystyle{ G}\) jest hamiltonowski. Zweryfikować to dla grafu o \(\displaystyle{ d=4}\).

Mógłby mi ktoś pomóc je rozwiązać? Za wszelkie wskazówki będę bardzo wdzięczny

Liczba krawędzi w grafie G to: \(\displaystyle{ \frac{d(2d-1)}{2}=d^2- \frac{d}{2}}\)
Ponieważ liczba krawędzi może być tylko liczbą naturalną to liczba d musi być parzysta.

Tw.
Graf prosty o k wierzchołkach jest hamiltonowskim gdy jego liczba krawędzi jest nie mniejsza niż \(\displaystyle{ {k-1 \choose 2}+2}\)

Wystarczy więc sprawdzić dla jakich d zachodzi:
\(\displaystyle{ {(2d-1)-1 \choose 2}+2 \le d^2- \frac{d}{2}}\)
stąd:
\(\displaystyle{ d \ge \frac{7}{4}}\)
czyli każdy G o parzystym d jest hamiltonowski.

Rysunki:
Moim zdaniem istnieją dwa nieizomorficzne grafy G o 7 wierzchołkach, z których wychodzą po 4 krawędzie. Narysuj je i wskaż na nich ścieżki Hamiltona.