Witam. Zgodnie z twierdzeniem Orego graf jest hamiltonowski jeśli \(\displaystyle{ st( V_{i}) \ge \frac{n}{2}}\). Jest to też taki graf, w którym możemy znaleźć cykl przechodzący dokładnie raz przez każdy wierzchołek.
Dlaczego w takim razie ten graf jest hamiltonowski pomimo, że np. lewy górny wierzchołek ma stopnień równy 2, co nie jest większe od \(\displaystyle{ \frac{5}{2}}\)?
Ostatnio zmieniony 13 maja 2013, o 19:16 przez placky, łącznie zmieniany 1 raz.