z Kamil: Za pomocą szufladkowej zasady Dirichleta, udowodnij ze każdy graf prosty ma co najmniej dwa wierzchołki o tym samym stopniu.

jc: Podpowiem, to łatwe zadanie.

Kamil: może być tak, że z lematu o uścisku dłoni wiadomo że jest dwa razy więcej wierzchołków niż krawędzi, więc jeśli krawędzie są szufladkami, a wierzcholki piłkami, to w i szufladce musi być przynajmniej 2 piłki?

jc: Załóżmy, że mamy n wierzchołków. Jeśli mamy wierzchołek stopnia n, to nie mamy wierzchołka stopnia 0 i odwrotnie. Zatem mamy n−1 możliwych stopni i n wierzchołków. Jakiś stopień musi się powtórzyć.

Kamil: Trochę nie łapię z tym stopniem n, gdyż graf nie może mieć n wierzchołków i mieć wierzchołek stopnia n.

jc: Masz rację. Miało być tak: Jeśli graf ma wierzchołek stopnia n−1, to nie ma wierzchołka stopnia 0 i odwrotnie. Dalej bez zmian.