Nie istnieje, z lematu o uściskach dłoni.
Nie istnieje, ponieważ jeżeli popatrzymy na wierzchołek o stopniu 4, to on ma krawędź z każdym innym. W tym momencie mamy ciąg stopni 1,1,1,1,4. Nie możemy stworzyć 2 krawędzi, aby jeden wierzchołek miał stopień o 2 większy, nie poruszając stopni innych wierzchołków. Nie zrobimy też cyklu, bo to graf prosty.
Jedyny prosty graf, o takim stopniu wierzchołków, to pięciokąt. Jest tam cykl o długości 5. Mamy twierdzenie mówiące, że każdy cykl w grafie dwudzielnym musi mieć długość parzystą.
Mamy graf G, a w nim wyróżnione x,y\in V(G):
\forall a,b\in V(G)\ \ d(x,y) \geq d(a,b), no i d(x,y)>3
Chcemy pokazać, że \forall a,b \in V(\overline{G})\ .\ d(a,b)\leq 2.
Weźmy dowolne a,b \in V(\overline{G}) i rozważmy dwa przypadki:
1° d(a,b)>1 w G - wtedy oczywiście \{a,b\} \not\in E(G), a więc \{a,b\} \in E(\overline{G}), czyli w \overline{G} jest d(a,b)=1\leq 2.
2° \{a,b\} \in E(G). Wiemy, że w G na pewno nie istnieją drogi x-a-b-y, x-b-a-y, ani tym bardziej x-a-y czy x-b-y, gdyż łączyłyby one x z y za pomocą nie więcej niż 3 krawędzi. Wobec tego w \overline{G} musi istnieć po co najmniej jednej krawędzi ze zbiorów: \{xa,by\},\ \{xb,ay\},\ \{xa,ya\},\ \{xb,yb\}. I w efekcie powstanie nam droga a-x-b lub a-y-b. Tak więc d(a,b)\leq 2.
Załóżmy nie wprost, że mamy drzewo, w którym istnieje para rozłącznych wierzchołkowo dróg a-b i c-d, a także para rozłącznych dróg a-c i b-d.
Zobaczmy, czy istnieje dokładnie jedna droga z a do d (drzewo to graf spójny bez cykli).
Załóżmy, że korzysta ona z drogi a-b (to jest drzewo i z a do b można dojśc dokładnie jedną drogą).
Wtedy, nie możemy znaleźć się w c przed osiągnięciem b, ponieważ droga a-b jest rozłączna z c-d.
Z b możemy teraz dojść do d, nie przechodząc przez c. Możemy iść dalej nie przechodząc już nigdy więcej przez b, drogą d-c, a następnie c-a. Znaleźliśmy się w a.
Cykl. Sprzeczność.
Wszystkich drzew o rozróżnialnych wierzchołkach jest n^{n-2} (Twierdzenie Cayleya, 1889*), więc dla n-1 wierzchołków - (n-1)^{n-3}.
Czyli weźmy takie n-1 wierzchołkowe drzewo (etykiety od 2 do n) i doczepmy do niego wierzchołek o etykiecie „1” (na n-1 różnych sposobów, bo doczepialmy do wierzchołka).
\displaystyle P = \frac {(n-1)\cdot(n-1)^{n-3}} {n^{n-2}}
\displaystyle \lim_{n\rightarrow \infty} \frac {(n-1)\cdot(n-1)^{n-3}} {n^{n-2}} = \lim_{n\rightarrow \infty} (1 - \frac 1 n)^{n-2} = \frac 1 e
Wskażemy odpowiednią ścieżkę definiując ją indukcyjnie.
Załóżmy, że istnieje ścieżka o długości \displaystyle k < r tzn. \displaystyle v_1\to v_2\to\ldots\to v_k.
Wierzchołek \displaystyle v_k ma co najmniej \displaystyle r sąsiadów, musi więc mieć sąsiada \displaystyle v_{k+1} poza \displaystyle k-elementowym zbiorem \displaystyle \left\lbrace v_1,v_2,\ldots,v_k \right\rbrace.
Skonstruowaliśmy więc ścieżkę \displaystyle v_1\to v_2\to\ldots\to v_k\to v_{k+1} odwiedzającą \displaystyle k+1 wierzchołków.
Powtarzając tę czynność tak długo jak \displaystyle k< r , otrzymujemy \displaystyle r-elementową ścieżkę:
\displaystyle v_1\to v_2\to\ldots\to v_r.
Wiemy więc, że ścieżka o możliwie największej długości ma \displaystyle k\geq r wierzchołków.
Niech \displaystyle w_1\to w_2\to\ldots\to w_k będzie taką ścieżką.
Z jej maksymalności wiemy, że wszyscy sąsiedzi \displaystyle w_k są już na tej ścieżce, bo inaczej można by ją było przedłużyć.
Niech więc \displaystyle w_i będzie sąsiadem \displaystyle w_k o najmniejszym indeksie.
Ścieżka \displaystyle w_i\to w_{i+1}\to\ldots\to w_k odwiedza \displaystyle r sąsiadów wierzchołka \displaystyle w_k, więc jest długości co najmniej równej \displaystyle r.
Wraz z wierzchołkiem \displaystyle w_k tworzy więc cykl:
\displaystyle w_i\to w_{i+1}\to\ldots\to w_k\to w_i.
o długości co najmniej \displaystyle r+1.