Jeśli \(\displaystyle{ \left|V(G) \right|\ge 5}\) i każdy podgraf indukowany w G przez 4 wierzchołki ma co najmniej 4 krawędzie to G ma cykl Hamiltona.
Może jakaś wskazówka? Z danych widać ,że każdy taki podgraf nie może być drzewem. Musi posiadać więc cykl. Ale co dalej?
Cykl hamiltona
-
bakala12
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
Cykl hamiltona
Wskazówka:
Wykaż lemat, że dla każdego wierzchołka \(\displaystyle{ deg v \ge n-2}\) gdzie \(\displaystyle{ n}\) to liczba wierzchołków w grafie i użyj twierdzenia Diraca.
Wykaż lemat, że dla każdego wierzchołka \(\displaystyle{ deg v \ge n-2}\) gdzie \(\displaystyle{ n}\) to liczba wierzchołków w grafie i użyj twierdzenia Diraca.
-
gardner
Cykl hamiltona
Robiłem podobne zadanie z dwuspójnością ale tutaj ciężej o jakąś sprzeczność.
Weźmy np. taki graf:
On nie spełnia założeń zadania,bo jak weźmiemy ten dolny wierzchołem i 3 górne to będą tylko 3 krawędzie,tak ?
Pewnie skoro doszedłem do tego , że graf nie może być drzewem i musi mieć cykl trzeba założyć ,że jakiś wierzchołek ma stopień 1 i dojść do sprzeczności z tym,że istnieją 4 krawędzie. Ten przykład jest dobry do rozpatrywania?
Weźmy np. taki graf:
On nie spełnia założeń zadania,bo jak weźmiemy ten dolny wierzchołem i 3 górne to będą tylko 3 krawędzie,tak ?
Pewnie skoro doszedłem do tego , że graf nie może być drzewem i musi mieć cykl trzeba założyć ,że jakiś wierzchołek ma stopień 1 i dojść do sprzeczności z tym,że istnieją 4 krawędzie. Ten przykład jest dobry do rozpatrywania?