Dwa różne wierzchołki grafu o tym samym stopniu

[rajban]

Udowodnij że w dowolnym grafie G istnieją dwa różne wierzchołki \(\displaystyle{ x, y \in V(G)}\) takie, że \(\displaystyle{ d(x)=d(y)}\).

Rozpatrywać każdy z przypadków grafu (regularny, dwudzielny, itd...) czy wyjść z jakiejś definicji?

[yorgin]

Wyjść z zasady szufladkowej Dirichleta.

[wiedzmac]

Dowód nie wprost. Załóżmy, że nie ma takich wierzchołków o równych stopniach.

Jeżeli mamy graf prosty o \(\displaystyle{ n}\) wierzchołkach to liczba krawędzi wychodzących z danego wierzchołka to \(\displaystyle{ 0, 1, \ldots n-1}\).

Zauważ, że nie może zajść taka sytuacja, że w grafie są wierzchołki o stopniu \(\displaystyle{ 0}\) i \(\displaystyle{ n-1}\), stąd jakaś para wierzchołków musi mieć równe stopnie.

QED.

PS: Tutaj powinno być założenie, że graf jest prosty, bo inaczej teza nie zachodzi.