Wykaż, że w dowolnym grafie liczba wierzchołków stopnia nieparzystego jest parzysta.
Dowód:
\(\displaystyle{ p,n}\) - odpowiednio wierzchołki o stopniu parzystym i nieparzystym
z Lematu o uściskach dłoni
\(\displaystyle{ \sum_{v \in V(G)} deg(v) = \sum_{v \in V_p(G)}deg(v) + \sum_{v \in V_n(G)} deg(v) = 2|E|}\)
gdzie\(\displaystyle{ |E|}\) jest liczbą krawędzi.
Wiemy, że pierwsza suma jest napewno parzysta, zatem druga suma też musi być parzysta, ponieważ prawa strona równania jest parzysta.
Skoro dla każdego wierzchołka w drugiej sumie, jego stopień jest nieparzysty, to aby druga suma była parzysta, musi być parzysta ilość tych wierzchołków.
Czy taki dowód byłby wystarczający?:)