Udowodnij, że dowolne drzewo

[max123321]

Udowodnij, że dowolne drzewo o parzystej liczbie krawędzi ma co najmniej jeden wierzchołek parzystego stopnia.

Jak to zrobić?

[MrCommando]

Weźmy dowolne drzewo \(\displaystyle{ T=(V,E)}\) o parzystej liczbie krawędzi. Wiemy, że zachodzi \(\displaystyle{ |E|=|V|-1}\) (ponieważ jest to drzewo). Skoro więc liczba krawędzi jest parzysta, to oznacza, że liczba wierzchołków jest nieparzysta. Przypuśćmy, że każdy wierzchołek ma nieparzysty stopień. Wówczas suma stopni w grafie \(\displaystyle{ T}\) jest liczbą nieparzystą, jako suma nieparzystej liczby liczb nieparzystych. Jest to oczywista sprzeczność z lematem o uściskach dłoni, który mówi, że \(\displaystyle{ \sum_{v\in V}\mbox{deg} v=2|E|}\). Zatem co najmniej jeden wierzcholek musi być stopnia parzystego.