Handshaking Lemma

The handshaking lemma is one of the most fundamental results in graph theory, providing a simple yet powerful relationship between vertex degrees and the number of edges. Despite its elementary nature, it has numerous applications and consequences throughout graph theory.

TheoremHandshaking Lemma

Let $G = (V, E)$ be a graph with $m$ edges. Then: $\sum_{v \in V} \deg(v) = 2m$

Equivalently, the sum of all vertex degrees equals twice the number of edges.

The proof counts each edge exactly twice: once from each endpoint. This double-counting argument is ubiquitous in combinatorics and graph theory.

Proof

Consider summing degrees over all vertices. Each edge $e = \{u,v\} \in E$ contributes exactly 2 to this sum: it contributes 1 to $\deg(u)$ and 1 to $\deg(v)$ . Since there are $m$ edges and each contributes 2 to the total, we have: $\sum_{v \in V} \deg(v) = 2m$

■

TheoremCorollary: Even Number of Odd Vertices

Every graph has an even number of vertices with odd degree.

Proof

Partition vertices into $V_{\text{odd}}$ (odd degree) and $V_{\text{even}}$ (even degree). Then: $\sum_{v \in V} \deg(v) = \sum_{v \in V_{\text{odd}}} \deg(v) + \sum_{v \in V_{\text{even}}} \deg(v)$

Since the left side equals $2m$ (even) and the second sum on the right is even (sum of even numbers), we have: $\sum_{v \in V_{\text{odd}}} \deg(v) \equiv 0 \pmod{2}$

As this is a sum of odd numbers that must be even, there must be an even number of terms, i.e., $|V_{\text{odd}}|$ is even.

■

ExampleApplication to Graph Non-Existence

Can we construct a graph with degree sequence $(3, 3, 3, 3, 3)$ ? The sum of degrees would be 15, which is odd. By the handshaking lemma, this is impossible since $2m$ must be even. Therefore, no such graph exists.

Remark

The handshaking lemma generalizes to directed graphs: $\sum_{v \in V} \deg^+(v) = \sum_{v \in V} \deg^-(v) = m$ , where $\deg^+(v)$ and $\deg^-(v)$ are the out-degree and in-degree respectively. This states that the total number of outgoing edges equals the total number of incoming edges, both equal to $m$ .

The handshaking lemma is often the first tool applied when analyzing degree sequences, counting arguments, and proving the impossibility of certain graph configurations. Its simplicity belies its power and utility throughout graph theory.