Graf Hamiltona

[lukabesoin]

Udowodnić że jeśli każde 3 wierzchołki indukuja podgraf o co najmniej 2 krawędziach to graf ma cykl Hamiltona(liczba wierzchołków >=4)

[miodzio1988]

Udowodnić że jeśli każde 3 wierzchołki indukuja podgraf o co najmniej 2 krawędziach to graf ma cykl Hamiltona(liczba wierzchołków >=4)

Niech:
\(\displaystyle{ \left|V(G) \right| =p}\)
Prawdziwa jest nierownosc:
\(\displaystyle{ \delta(G) \ge 2}\)
Gdyby nie była prawdziwa to każde 3 wierzchołki nie indukowałyby podgrafu o podanych wyzej wlasnosciach.
Rowniez prawdą jest to, że:
\(\displaystyle{ \delta(G) \ge p-1 \ge \frac{p}{2}}\)
(tutaj trzeba się zastanowić czy tych nierownosci trzeba nie "polepszyc")
Graf \(\displaystyle{ G}\)spełnia załozenia Tw Diraca zatem posiada cykl Hamiltona.
Prosze sie czepiac wszystkiego co jest w dowodzie- w ten sposob go udoskonalimy

[xiikzodz]

Niech

\(\displaystyle{ G=\langle V=\{v_1,...,v_n\},E\rangle}\)

Wybierzmy w grafie dowolny wierzchołek \(\displaystyle{ v\in V}\). Zauważmy, że spośród pozostałych wierzchołków istnieje co najwyżej jeden, z którym wierzchołka \(\displaystyle{ v}\) nie łączy krawędź. W przeciwnym razie, to jest gdyby istniały dwa, powiedzmy \(\displaystyle{ u,w}\), wierzchołki \(\displaystyle{ u,v,w}\) indukowałyby podgraf mający co najwyżej jedną krawędż łączącą \(\displaystyle{ u}\) z \(\displaystyle{ w}\). Zatem minimalny stopień wierzchołka w grafie jest nie mniejszy niż \(\displaystyle{ n-2}\) (znaczy się \(\displaystyle{ \delta(G)\ge n-2}\)).

Można teraz użyć twierdzenia Diraca, które gwarantuje, że w grafie \(\displaystyle{ G}\) znajdziemy cykl długości przynajmniej \(\displaystyle{ \min(n,2(n-2))}\) co dla \(\displaystyle{ n\ge 4}\) oznacza, że znajdziemy cykl długości przynajmniej \(\displaystyle{ n}\) czyli Hamiltona.

Natychmiastowy argument bez tw. Diraca: przez indukcję:

Dla \(\displaystyle{ n=4}\) na piechotę. W grafie o \(\displaystyle{ n>4}\) wierzchołkach wybieramy jeden, powiedzmy \(\displaystyle{ v}\). Z założenia indukcyjnego graf \(\displaystyle{ G-v}\) jest hamiltonowski i ma przynajmniej \(\displaystyle{ 4}\) wierzchołki spośród których znajdziemy dwa kolejne (w cyklu Hamiltona) połączone krawędzią z \(\displaystyle{ v}\) . A to z kolei oznacza, że cykl w grafie \(\displaystyle{ G-v}\) można przedłużyć do cyklu w \(\displaystyle{ G}\).