Handshaking Lemma

Statement

Let $G=(V,E)$ be a finite undirected graph (no assumptions on simplicity). Then \[ \sum_{v\in V}\deg(v) = 2|E|. \]

Proof

Count the set \[ S:=\{(v,e)\in V\times E : \text{$e$ is incident to $v$}\}. \] Fix $v\in V$. The number of pairs in $S$ with first coordinate $v$ is $\deg(v)$. Hence \[ |S| = \sum_{v\in V}\deg(v). \]

Fix an edge $e\in E$. In an undirected graph, $e$ has exactly two endpoints, so $e$ contributes exactly two incident pairs in $S$ (one for each endpoint). Therefore \[ |S| = 2|E|. \] Combining the two expressions for $|S|$ gives \[ \sum_{v\in V}\deg(v) = 2|E|. \]

Corollary

The number of vertices of odd degree is even.

Let $O:=\{v\in V:\deg(v)\ \text{is odd}\}$. Reduce the identity \[ \sum_{v\in V}\deg(v) = 2|E| \] modulo $2$. The right hand side is $0\pmod 2$, hence \[ \sum_{v\in V}\deg(v)\equiv 0\pmod 2. \] Even degree terms vanish modulo $2$, so \[ \sum_{v\in O}\deg(v)\equiv |O|\pmod 2, \] since each odd $\deg(v)\equiv 1\pmod 2$. Thus $|O|\equiv 0\pmod 2$, i.e. $|O|$ is even.