Proof that the number of odd-degree vertices is even

Proof

1. Let $V$ be the vertex set and $E$ the edge set of $G$. Let $V_o$ be the set of vertices of odd degree, and $V_e = V \setminus V_o$ the set of vertices of even degree.
2. By the handshaking lemma, $\sum_{v \in V} \deg(v) = 2 \abs{E}$, which is even.
3. The sum $\sum_{v \in V_e} \deg(v)$ is a sum of even numbers, so it is even.
4. Hence $\sum_{v \in V_o} \deg(v) = 2\abs{E} - \sum_{v \in V_e} \deg(v)$ is even.
5. Each term of the sum in step 4 is odd, so it is congruent to $1$ modulo $2$. Thus that sum is congruent to $\abs{V_o}$ modulo $2$.
6. By steps 4 and 5, $\abs{V_o}$ is even.