Twierdzenie Ore

[Dexous]

Mam problem ze zrozumieniem dowodu Twierdzenia Orego.
Wiem ze mozemy skonstruowac tak sciezke ze bedzie to najdluzsza sciezka, taka ze jak dolozymy jedna krawedz to powstanie cykl Hamiltona), a wiec poki co istnieje sciezka Hamiltona.
\(\displaystyle{ v_1 \to v_2 \to \ldots \to v_n}\)

I teraz w wiekszosci dowodow jest wniosek ze musi istniec wierzcholek \(\displaystyle{ v_i}\) ktory jest sasiadem z \(\displaystyle{ v_1}\) oraz wierzcholek \(\displaystyle{ v_{i-1}}\) ktory jest sasiadem dla wierzcholka \(\displaystyle{ v_n}\) i w ten sposob otrzymujemy cykl Hamiltona, co jest sprzeczne z zalozeniem i koniec dowodu.

I teraz pytanie dlaczego musi istniec taki wierzcholek \(\displaystyle{ v_i}\) oraz \(\displaystyle{ v_{i-1}}\)

[Qń]

Wiemy, że \(\displaystyle{ v_1}\) nie jest połączone z \(\displaystyle{ v_n}\), wiemy też, że \(\displaystyle{ v_1}\) jest połączone z \(\displaystyle{ v_2}\), a \(\displaystyle{ v_n}\) z \(\displaystyle{ v_{n-1}}\). Pozostali sąsiedzi \(\displaystyle{ v_1}\) znajdują się w zbiorze \(\displaystyle{ \{v_3, v_4, \ldots , v_{n-1}\}}\), a pozostali sąsiedzi \(\displaystyle{ v_n}\) w zbiorze \(\displaystyle{ \{v_2,v_3, \ldots , v_{n-2}\}}\). Potencjalnie mogą się jeszcze pojawić krawędzie \(\displaystyle{ v_1v_i}\) dla \(\displaystyle{ i=3,4,\ldots , n-1}\) oraz \(\displaystyle{ v_{i}v_n}\) dla \(\displaystyle{ i=2,3, \ldots , n-2}\). Wiemy jednak z założenia, że łączna ilość krawędzi o końcu w \(\displaystyle{ v_1}\) lub \(\displaystyle{ v_n}\) to co najmniej \(\displaystyle{ n}\), zatem wśród powyższych musi być ich co najmniej \(\displaystyle{ n-2}\).

Jeśli sparujemy te potencjalne krawędzie w następujący sposób:
\(\displaystyle{ \{v_1v_i, v_{i-1}v_n\}}\) gdzie \(\displaystyle{ i=3,4, \ldots , n-1}\)
to dostaniemy \(\displaystyle{ n-3}\) par. Skoro zaś krawędzi jest co najmniej \(\displaystyle{ n-2}\), to na mocy Zasady Szufladkowej Dirichleta w naszym grafie muszą być obie krawędzie z pewnej pary, a tego właśnie chcieliśmy.

Q.

[Dexous]

Ok dzieki wielkie, zrozumialem.