Number of graph vertices of odd degree is even

Question

This elementary result is normally stated as a corollary to the Handshaking Lemma, which says nothing about it other than that it's true. I wonder if there is more depth to this fact, in particular if there are any essentially different proofs and/or arguments visualizing why this should be true... Thanks!

Answer 1

The handshaking lemma states that for every graph $G=(V,E)$: $$ \sum_{v\in V}\deg(v)=2m, $$ so the sum $\sum_{v\in V}\deg(v)$ has to be even. This sum can be decomposed in two sums: $$ \sum_{v\in V}\deg(v)=\sum_{v\in V|\deg(v)=2k}\deg(v)+\sum_{v\in V|\deg(v)=2k+1}\deg(v), $$ The first is clearly even, so the second one also has to be even. But if $deg(v)=2k+1$, than the number of such vertices has to be even (as an odd number of odd terms cannot be even).

Answer 2

Assume you have a simple finite connected graph $G$ with number of vertices $V$, number of edges $E$, and with degrees $d_1,d_2, \dots,d_V$ for corresponding vertices $v_1, v_2, \dots, v_V$. Since G is simple and finite, we know that $\sum_{i=1}^{V}d_i=2E$, meaning that the sum of degrees must be an even number. If we add up even degrees, we will always get an even number. If we add up odd degrees we will only get an even number if we add up an even number of odd degrees. Therefore there must be an even number of odd degree vertices.