Handshaking lemma

Statement

Let $G$ be a finite graph with vertex set $V$ and edge set $E$. Then $$\sum_{v \in V} \deg(v) = 2\, |E|.$$

Remarks

Proof: count the pairs $(v, e)$ with $v \in e$. Each edge has two ends, and each vertex $v$ lies in $\deg(v)$ edges. This is double counting. A direct consequence is that the number of odd-degree vertices is even. For a $3$-regular graph on $n$ vertices, it gives $3n = 2 |E|$, so $n$ is even.

Explanations

L1 human

At a party, add up the number of hands each person shakes. Each handshake is counted twice, once for each of the two people, so the total is twice the number of handshakes.