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

Beweis

Es sei ${}V_{g}$ die Knoten mit einem geraden Grad und ${}V_{u}$ die Knoten mit einem ungeraden Grad. Nach Fakt gilt

${}\sum _{v\in V_{g}}d(v)+\sum _{v\in V_{u}}d(v)=2\cdot {\#\left(E\right)}\,,$

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 ${}V_{u}$ gerade ist.

Zur bewiesenen Aussage