Skip to main content

Short note: Handshaking theorem

Short answer

The handshaking theorem: the sum of the degrees of all vertices in an undirected graph equals twice the number of edges (∑ deg(v) = 2e). Corollaries: the degree sum is even, there is an even number of odd-degree vertices, and a k-regular graph on n vertices has nk/2 edges.

Write a short note on the Handshaking Theorem for undirected graphs (state the theorem).

Statement: Let G = (V, E) be an undirected graph with e edges. Then the sum of the degrees of all vertices equals twice the number of edges:

Σ_{v∈V} deg(v) = 2e

This holds even with multiple edges and loops (a loop adds 2 to the degree of its vertex).

Reason: each edge connects two vertices (or one, for a loop), contributing 1 to each endpoint's degree, so each edge is counted twice in the sum.

Corollaries:

  • The sum of the degrees is always even.
  • The number of vertices of odd degree is even.
  • A k-regular graph on n vertices has nk/2 edges.

Example: A graph with 5 edges has degree sum 10, for instance degrees 3, 3, 2, 1, 1 (four odd vertices, an even number). A graph on 4 vertices with degrees 3, 3, 3, 3 has 6 edges (K₄).

Directed version: the sum of in-degrees = sum of out-degrees = number of edges.

Use: checking whether a given degree sequence can be a graph; counting edges.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →