Wykaż, że... graf spójny - wierzchołki - jednakowe stopnie

[gabilu]

Wykazać, że w spójnym grafie prostym o 8 wierzchołkach istnieją co najmniej dwa wierzchołki jednakowych stopni.
Wskazówka: Założyć, że pewnych siedem wierzchołków tego grafu ma różne stopnie. Jakie to muszą być stopnie? Wywnioskować informacje o stopniu ostatniego wierzchołka.

Bardzo proszę o pokazanie, jak udowodnić tą tezę. Będę bardzo wdzięczna -- 12 kwi 2016, o 13:14 --Zgodzicie się ze mną?

Z: mamy spójny graf o 8 wierzchołkach
T: istnieją co najmniej 2 wierzchołki jednakowych stopni
D: załóżmy, że pewnych 7 wierzchołków tego grafu ma różne stopnie. Gdybyśmy chcieli, żeby każdy wierzchołek naszego grafu miał różny stopień, to zaczynając próbę wyznaczania tych stopni od największego możliwego do uzyskania tzn. st.6, to zauważamy, że kolejny musiałby mieć: st.5, st.4, st.3, st.2, st.1 i ... brakuje nam liczby, ponieważ kończymy liczyć stopnie na 1, a został nam jeszcze jeden wierzchołek, któremu nie przydzieliliśmy stopnia będącego różnym od pozostałych. Nie możemy mu przydzielić st.0, bo rozpatrujemy graf spójny prosty, co oznacza, że graf musi mieć przynajmniej 2 wierzchołki tego samego stopnia. Analogicznie odbywa się to w grafie spójnym prostym o 8 wierzchołkach, co kończy dowód.

[Hubbaser]

OK, ale troszkę przegadane

Masz 8 wierzchołków i 7 możliwych stopni. Z zasady szufladkowej 2 wierzchołki mają ten sam stopień.

BTW zasada szufladkowa to oczywistość, ale warto się na nią powoływać, by się nie napisać