Skip to main content

Handshaking theorem; even number of odd vertices

Short answer

The handshaking theorem: sum of degrees = 2e. Proof of even number of odd-degree vertices: split vertices into even-degree and odd-degree sets. The sum of all degrees (2e) and sums from even-degree vertices are even, so the sum of odd-degree terms is even. Since each term is odd, the count of odd-degree vertices must be even.

State the handshaking theorem for the undirected graph and use it to prove the theorem that an undirected graph has an even number of vertices of odd degree.

Handshaking theorem

If G = (V, E) is an undirected graph with e edges, then

Σ over v ∈ V of deg(v) = 2e.

Reason: each edge has two endpoints, so it adds exactly 1 to the degree of each of its two end vertices (a loop adds 2 to its single vertex). Counting all degrees counts every edge twice.

Theorem: an undirected graph has an even number of vertices of odd degree

Proof. Let V₁ be the set of vertices of even degree and V₂ the set of vertices of odd degree. By the handshaking theorem,

2e = Σ_{v∈V} deg(v) = Σ_{v∈V₁} deg(v) + Σ_{v∈V₂} deg(v).

  1. 2e is even.
  2. Σ_{v∈V₁} deg(v) is a sum of even numbers, so it is even.
  3. Therefore Σ_{v∈V₂} deg(v) = 2e − Σ_{v∈V₁} deg(v) is even (difference of two even numbers).
  4. Every term in this last sum is odd. A sum of odd numbers is even only if the number of terms is even.
  5. Hence |V₂|, the number of vertices of odd degree, is even. ∎

Example: a graph with degrees 3, 3, 2, 2, 4 has 14 = 2·7 as degree sum, 7 edges, and two (even number) odd vertices.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Discrete Structure chapter 4 questions →