Mathwords logoMathwords

Handshaking Lemma — Definition, Formula & Example

The Handshaking Lemma is the fact that if you add up the degrees of all the vertices in an undirected graph, you get exactly twice the number of edges. The name comes from a party: if you add up how many hands each guest shook, every handshake is counted twice.

Let G=(V,E)G = (V, E) be a finite undirected graph. Multiple edges are allowed, and a loop contributes 2 to the degree of its vertex. Then ∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|. Corollary: every finite undirected graph has an even number of vertices of odd degree.

Key Formula

∑v∈Vdeg⁡(v)=2∣E∣\sum_{v \in V} \deg(v) = 2|E|
Where:
  • VV = The set of vertices of the graph
  • deg⁡(v)\deg(v) = The degree of vertex v, which is the number of edge endpoints at v (a loop counts 2)
  • ∣E∣|E| = The number of edges in the graph

How It Works

The proof uses double counting. Count the pairs (v, e) where vertex v is an endpoint of edge e. Counting by vertices, vertex v appears in exactly deg(v) pairs, so the total is the sum of the degrees. Counting by edges, each edge has exactly two endpoints (a loop counts its vertex twice), so the total is 2|E|. Both counts describe the same set, so they are equal. For the corollary, the even-degree vertices contribute an even amount to the sum. The odd-degree vertices must then also sum to an even number, and that can only happen if there is an even number of them.

Worked Example

Problem: A graph has 15 edges. Four of its vertices have degree 5, and every other vertex has degree 2. How many vertices does the graph have?
Step 1: Apply the Handshaking Lemma to find the total degree.
∑v∈Vdeg⁡(v)=2∣E∣=2×15=30\sum_{v \in V} \deg(v) = 2|E| = 2 \times 15 = 30
Step 2: The four degree-5 vertices contribute 20 of that total. Let k be the number of degree-2 vertices, which together contribute 2k.
4×5+2k=30  ⟹  2k=10  ⟹  k=54 \times 5 + 2k = 30 \implies 2k = 10 \implies k = 5
Step 3: Add the two groups of vertices.
∣V∣=4+5=9|V| = 4 + 5 = 9
Answer: The graph has 9 vertices: 4 of degree 5 and 5 of degree 2.

Why It Matters

In a discrete math or graph theory course, the lemma is often the quickest way to show that a graph cannot exist. For example, no group of 7 people can each be friends with exactly 3 others, because 7×3=217 \times 3 = 21 is odd. It also gives edge counts directly, such as ∣E∣=rn2|E| = \frac{rn}{2} for an r-regular graph on n vertices. In addition, it supports results about Euler paths, where the number of odd-degree vertices is what matters.

Common Mistakes

Mistake: Concluding that a list of degrees forms a simple graph just because the degrees add up to an even number.
Correction: An even sum is necessary but not sufficient. The sequence 3, 3, 1, 1 sums to 8, but no simple graph has these degrees. Each degree-3 vertex would have to be adjacent to all three other vertices, which forces the last two vertices to have degree at least 2. To test a degree sequence for a simple graph, use the Havel–Hakimi algorithm or the Erdős–Gallai theorem.

Related Terms

  • Lemma — The kind of helper result this statement is
  • Pseudograph — Shows why loops add 2 so the lemma holds
  • Bipartite Graph — Degrees on each side separately sum to the edge count
  • Clique — Lemma gives its edge count n(n-1)/2
  • Acyclic Graph — A forest with n vertices and c components has degree sum 2(n − c)
  • Handshake Problem — Party counting puzzle that inspires the lemma's name
  • Degree Sequence — Lemma shows degree sequence sums must be even