Graf spójny.

[snowjay]

Hej.
Mam następujące zadanie do zrobienia:

Niech G będzie grafem z n wierzchołkami. Każdy wierzchołek ma stopień przynajmniej większy od \(\displaystyle{ \frac{n-1}{2}}\). Pokazać, że graf jest spójny. WSK: Przyjąć, że G nie jest spójny.

Dziękuję za pomoc.

[Qń]

Każdy wierzchołek ma stopień przynajmniej większy od \(\displaystyle{ \frac{n-1}{2}}\)

Chyba raczej: równy przynajmniej \(\displaystyle{ \frac{n-1}{2}}\).

Pokażemy, że dowolne dwa wierzchołki tego grafu są połączone krawędzią lub istnieje trzeci wierzchołek, z którym oba są połączone. Oczywiście wystarczy to do wykazania spójności, bo oznacza to, że między dowolnymi dwoma wierzchołkami istnieje droga.

Weźmy zatem dwa dowolne wierzchołki. Jeśli są połączone krawędzią to już koniec, a jeśli nie są, to zauważmy, że od tych wierzchołków odchodzi w sumie co najmniej \(\displaystyle{ \frac{n-1}{2}+\frac{n-1}{2}=n-1}\) krawędzi. Ale końcami każdej z krawędzi jest któryś z pozostałych \(\displaystyle{ n-2}\) wierzchołków, zatem pewne dwie z tych krawędzi mają wspólny koniec (formalnie wynika to z Zasady Szufladkowej Dirichleta). Ten wspólny koniec to właśnie ten trzeci wierzchołek, którego istnienia mieliśmy dowieść.

Q.