Handshaking lemma proof

Show that the number of vertices of odd degree in a graph is always even.

Proof (Handshaking lemma / parity argument)

Let $G=(V,E)$ be a finite graph. For each vertex $v\in V$ let $\deg(v)$ denote its degree. Two standard facts:

1. Each edge contributes exactly $2$ to the total sum of degrees (one for each endpoint). Hence

$$ \sum_{v\in V}\deg(v)=2|E|, $$

so the total sum of degrees is even.

2. Split the vertex set $V$ into $V_{\text{even}}$ (vertices of even degree) and $V_{\text{odd}}$ (vertices of odd degree). The sum of degrees over $V_{\text{even}}$ is even (sum of even numbers). Therefore the parity of the whole sum equals the parity of the sum over $V_{\text{odd}}$. But the sum of $k$ odd numbers has the same parity as $k$ (odd sum iff $k$ is odd). Thus

$$ \sum_{v\in V}\deg(v)\ \text{is even} \quad\Longrightarrow\quad |V_{\text{odd}}|\ \text{is even}. $$

So the number of vertices of odd degree must be even. ∎