Ungerichteter Graph/Anzahl/Ungerader Grad/Gerade/Fakt/Beweis

Aus Wikiversity
Zur Navigation springen Zur Suche springen
Beweis

Es sei die Knoten mit einem geraden Grad und die Knoten mit einem ungeraden Grad. Nach Fakt gilt

diese Zahl ist also gerade. Der linke Summand ist als Summe von geraden Zahlen ebenfalls gerade. Somit muss auch der rechte Summand gerade sein. Dies kann nur sein, wenn die Anzahl von gerade ist.