Graf hamiltonowski - dowód

[piotrekgym]

Niech \(\displaystyle{ G=(V,E)}\) będzie grafem, takim że \(\displaystyle{ |V| \ge 4}\) oraz dla dowolnych wierzchołków u,v,w co najmniej dwie spośród krawędzi uv, uw, i vw należą do E. Pokazać, że G jest hamiltonowski.

Prosiłbym o jakąś wskazówkę.

[Downonmyluck]

Weź dwa dowolne nieincydentne wierzchołki u,v grafu i rozpatrz dowolną trójkę u,v,w. Udowodnij, że spełniony jest warunek Orego, czyli graf jest hamiltonowski.

[piotrekgym]

Mógłbyś coś więcej napisać, bo nie bardzo wiem jak udowodnić że spełniony jest warunek Orego.

[Downonmyluck]

Weźmy dowolne \(\displaystyle{ u,v \in V}\) takie, że \(\displaystyle{ uv \not\in E}\). Jeśli takie wierzchołki nie istnieją, to graf jest grafem pełnym, więc z oczywistych względów istnieje cykl Hamiltona. Rozpatrzmy teraz dowolną trójkę \(\displaystyle{ u,v,w \in V}\). Z warunków zadania \(\displaystyle{ \forall w \in V \setminus \left\{u,v \right\} uw \in E vw \in E}\). Takich trójek jest \(\displaystyle{ n-2}\), zatem mamy spełnioną nierówność
\(\displaystyle{ deg u + deg v \ge 2n - 4 \ge n}\), bo liczba wierzchołków jest większa lub równa 4. Zatem jest spełniony warunek Orego, dzięki czemu graf jest hamiltonowski.