Witam, mam problem z następującym twierdzeniem:
Jeżeli graf prosty \(\displaystyle{ G}\) ma \(\displaystyle{ n}\) wierzchołków \(\displaystyle{ (n \geq 3)}\) oraz dla każdej pary niesąsiednich wierzchołków v,w (x≠w) zachodzi nierówność:
\(\displaystyle{ deg(v) + deg(w) \geq n}\)
to graf G jest hamiltonowski.
Dowód (nie wprost):
Przypuśćmy, że \(\displaystyle{ G}\)spełnia założenia twierdzenia lecz nie jest hamiltonowski. Powtarzamy tak długo jak to możliwe następującą procedurę: Jeżeli można dodać nową krawędź w taki sposób, żeby otrzymany graf nadal nie był hamiltonowski, to dodajemy ją (otrzymamy graf prosty). Graf Kn jest hamiltonowski, więc nasze postępowanie musi się skończyć przed otrzymaniem Kn. Otrzymamy graf G′ taki, że G′ jest prosty, nie jest hamiltonowski lecz po dodaniu jakiej kolwiek nowe krawędzi otrzymamy graf hamiltonowski. G′ jest półhamiltonowski i spełnia nierówność \(\displaystyle{ deg(v) + deg(w) \geq n}\)dla niesąsiednich wierzchołów v, w (v ≠ w). Niech v\(\displaystyle{ 1, v2, ... , vn}\)będzie drogą hamiltona w G′, \(\displaystyle{ v1}\), \(\displaystyle{ vn}\)nie są sąsiednie.
(*) istnieje \(\displaystyle{ 1<i<n}\)takie, że vi sąsiaduje z vn, a vi+1 sąsiaduje z v1
Przypuśćmy, że (*) jest fałszywe. Dla każdego wierzchołka vi sąsiadującego z vn wierzchołek vi+1 nie sąsiaduje z v1. Niech\(\displaystyle{ k=deg(vn)}\)w G′. Wówczas przynajmniej k wierzchołków v2, ... , vn nie sąsiaduje z v1. Zatem
\(\displaystyle{ deg(v_1) \leq n-1-k}\)
\(\displaystyle{ deg(v_1) + deg(v_n) \leq n-1-k+k = n-1}\)
wbrew nierówności w założeniu, sprzeczność, (*) jest prawdziwa. Znaleźliśmy cykl hamiltona w G′. Sprzeczność G jest hamiltonowski.
Mam problem ze zrozumieniem (*), zakładamy, że \(\displaystyle{ k=deg(vn)}\), wówczas przynajmniej k wierzchołków v2, ... , vn nie sąsiaduje z v1. Moje pytanie dlaczego nie muszą sąsiadować?
Z góry dzięki za pomoc.