Graf hamiltonowski

[michals95]

Niech \(\displaystyle{ G = (V,E)}\) będzie grafem majączym co najmniej 4 wierzchołki oraz spełniającym \(\displaystyle{ (\forall A \subseteq V)(\left| A\right|=3 \Rightarrow |{A\choose 2} \cap E| > 1)}\). Wykazać, że \(\displaystyle{ G}\) jest grafem hamiltonowskim.
Wydaje mi się, że warunek oznacza, że pomiędzy każdymi wierzchołkami w grafie G istnieją co najmniej dwie krawędzie. Nie wiem, czy jest to właściwe, bo np. dla 6 wierzchołków dostawałem \(\displaystyle{ K_{6}}\)

[hannahannah]

Ten warunek oznacza, że dla każdych trzech wierzchołków \(\displaystyle{ v_1,v_2,v_3}\) istnieją w grafie co najmniej dwie krawędzie spośród trzech możliwych \(\displaystyle{ (v_i,v_j)}\). Zauważ, że to oznacza, że każdy wierzchołek danego grafu jest połączony krawędzią z każdym innym poza co najwyżej jednym. Dlatego łatwo zadanie rozwiązać indukcją. Najpierw sprawdzamy, że dla czterech wierzchołków teza jest prawdziwa. To znaczy, że graf \(\displaystyle{ K_4}\) z usuniętymi dwoma krawędziami nie spotykającymi się w jednym wierzchołku jest hamiltonowski. Faktycznie, jest to cykl. Każdy graf czteroelementowy spełniający warunki zadania zawiera taki graf, czyli cykl czteroelementowy, więc mamy warunek początkowy indukcji. A dalej już łatwo. Zakładamy, że grafy spełniające założenia mające co najwyżej \(\displaystyle{ n}\) wierzchołków są hamiltonowskie. Rozważmy graf \(\displaystyle{ G}\) spełniający założenia mający \(\displaystyle{ n+1}\) wierzchołków. Wybieramy jeden wierzchołek, powiedzmy \(\displaystyle{ v_0}\). Graf powstały przez wyrzucenie \(\displaystyle{ v_0}\) jest na mocy założenia indukcyjnego hamiltonowski, więc ma cykl \(\displaystyle{ (v_1,v_2,\ldots,v_n)}\). Wierzchołek \(\displaystyle{ v_0}\) jest połączony krawędzią z co najmniej \(\displaystyle{ n-1}\) wierzchołkami tego cyklu, powiedzmy z wierzchołkami \(\displaystyle{ v_1,\ldots,v_{n-1}}\). Wtedy jednak \(\displaystyle{ (v_1,v_0,v_2,v_3,\ldots,v_n)}\) jest cyklem w \(\displaystyle{ G}\) i teza pokazana.