Grafy, ten sam stopień.

[MPIS_pad]

Jak wykazać, że w każdym grafie o co najmniej 2 wierzchołkach istnieją co najmniej 2 wierzchołki tego samego stopnia?

[leg14]

Jeżeli graf ma \(\displaystyle{ n}\) wierzchołków, to możliwe stopnie to \(\displaystyle{ 0,...,n-1}\). Załóżmy, że teza jest nieprawdziwa, czyli istnieje graf stopnia \(\displaystyle{ n}\) w którym każde dwa wierzchołki mają różny stopień. Niech \(\displaystyle{ A}\) oznacza zbiór stopniów wierzchołków tego grafu. twierdzę, że \(\displaystyle{ A = \left\{ 0,..,n-1\right\}}\). W szczególności istnieje wierzchołek stopnia zero. Możemy go odrzucić i otrzymać graf o \(\displaystyle{ n-1}\) wierzchołkach, który nadal nie spełnia (przeczy) tezy.

[kerajs]

Ciut inaczej:
Aby każdy wierzchołek grafu o \(\displaystyle{ n}\) wierzchołkach miał inny stopień to musi przyjąć on jedną (i różną od innych wierzchołków) z \(\displaystyle{ n}\) wartości od \(\displaystyle{ 0}\) do \(\displaystyle{ n-1}\). Jednak istnienie wierzchołka stopnia \(\displaystyle{ n-1}\) połączonego krawędziami z pozostałymi wierzchołkami grafu wyklucza istnienie wierzchołka stopnia \(\displaystyle{ 0}\) , i odwrotnie: istnienie wierzchołka stopnia \(\displaystyle{ 0}\) niepołączonego krawędziami z pozostałymi wierzchołkami grafu wyklucza istnienie wierzchołka stopnia \(\displaystyle{ n-1}\) . Ogranicza to ilość dostępnych stopni wierzchołków do \(\displaystyle{ n-1}\), więc przynajmniej dwa wierzchołki muszą mieć przypisany ten sam stopień.