Handshaking lemma

The Handshaking lemma states that any finite undirected graph has an even number of vertices with odd-degree. This follows immediately from a more fundamental result, namely, the degree sum formula.

Degree sum formula: Given an undirected graph $G$, with the set of vertices $V$ and edges $E$, we have$$\sum_{v \in V} \text{deg}(v) = 2\vert E \vert$$ If the graph has loops, i.e., an edge connecting the same vertex the above still holds true, provided we interpret that every loop counts to the degree of the vertex twice. (Sometimes, degree sum formula is also called the handshaking lemma)

Proof: We will prove the result when the graph has no loops. Once we prove it for graphs with no loops, the result is evident for graphs with loops since every time we add a loop, the degree of a vertex increases by $2$ and so does the right hand side.

Let $\mathbb{I}(v_i,v_j)$ be the indicator function that denotes if there is an edge between the vertices $v_i$ and $v_j$. We then have
$$\sum_{v_i \in V;v_j \in V} \mathbb{I}(v_i,v_j) = 2 \vert E \vert \tag{$\star$}$$This is because each edge is incident to two vertices and hence each edge is counted twice in the above summation. However, $(\star)$ can also be rewritten as $$\sum_{v_i \in V} \left(\sum_{v_j \in V} \mathbb{I}(v_i,v_j)\right) = 2 \vert E \vert$$Now note that $\displaystyle \left(\sum_{v_j \in V} \mathbb{I}(v_i,v_j) \right)$ is nothing but the degree of the vertex $v_i$, since each time a vertex is adjacent to the vertex $v_i$, the count increases by $1$. Hence, we have what we want, i.e.,$$\sum_{v \in V} \text{deg}(v) = 2\vert E \vert$$This immediately implies that there has to be an even number of vertices with odd-degree. Let $V_e$ be the set of vertices with even degree and $V_o$ be the set of vertices with odd degree. We then have that$$\sum_{v \in V_e} \text{deg}(v) + \sum_{v \in V_o} \text{deg}(v) = 2\vert E \vert \tag{$\dagger$}$$Since every vertex in $V_e$ has an even degree, we have $\sum_{v \in V_e} \text{deg}(v)$ to be an even number. This and $(\dagger)$ implies $\sum_{v \in V_o} \text{deg}(v) \,\,\, (\perp)$ has to be even. Now each of $\deg(v)$ in $(\perp)$ is odd. If $\vert V_o \vert$ were to be odd, then $\sum_{v \in V_o} \text{deg}(v)$ will be odd (since an odd number of odd integers when added up will give an odd number), contradicting the fact that it has to be even.