Handshaking Lemma
Introduction
The Handshaking Theorem, also called the Handshaking Lemma or the Sum of Degree Theorem, is a fundamental result in graph theory.
In an undirected graph, the theorem states that the sum of degrees of all vertices equals twice the number of edges.
Handshaking Theorem - Formal Statement
Let G = (V, E) be a finite undirected graph with vertex set V and edge set E. For each vertex v ∈ V let deg(v) denote its degree. Then
∑v∈V deg(v) = 2·|E|
Intuition and Proof
Each edge in an undirected graph has two ends and contributes exactly 1 to the degree of each of its two incident vertices.
Therefore each edge contributes exactly 2 to the sum of degrees of all vertices.
Summing the contributions of all edges gives:
Sum of degrees of all vertices = 2 × Number of edges.
Immediate Consequences
- The sum of degrees of all vertices in any graph is always even.
- The sum of degrees of the vertices that have odd degree is always even.
- Therefore, the number of vertices of odd degree in any graph is even.
Remarks and Related Points
- Loops contribute 2 to the degree of a vertex because the loop has both ends at the same vertex; this is consistent with the theorem.
- For directed graphs, the analogous statement is that the sum of all in-degrees equals the sum of all out-degrees equals the number of directed edges.
- The theorem applies to multigraphs (graphs with multiple edges) provided degrees count multiplicity in the usual way.
- The parity consequence (even number of odd-degree vertices) is often useful in existence arguments, for example in proving that an Eulerian trail exists only when 0 or 2 vertices have odd degree.
Practice Problems Based on Handshaking Theorem in Graph Theory
Problem 1: A simple graph G has 24 edges and degree of each vertex is 4. Find the number of vertices.
Given
- Number of edges = 24
- Degree of each vertex = 4
Let the number of vertices be n.
By the Handshaking Theorem, the sum of degrees of all vertices equals 2 × number of edges.
Sum of degrees = n × 4.
Therefore, n × 4 = 2 × 24.
So, 4n = 48.
Hence, n = 48 ÷ 4 = 12.
Thus, the number of vertices is 12.
Problem 2: A graph contains 21 edges, 3 vertices of degree 4 and all other vertices of degree 2. Find total number of vertices.
Given
- Number of edges = 21
- Number of degree 4 vertices = 3
- All other vertices are of degree 2
Let the total number of vertices be n.
By the Handshaking Theorem, the sum of degrees of all vertices equals 2 × number of edges.
Sum of degrees = (3 × 4) + (n - 3) × 2.
Therefore, 12 + 2(n - 3) = 2 × 21.
So, 12 + 2n - 6 = 42.
Hence, 2n + 6 = 42.
Thus, 2n = 36.
Therefore, n = 18.
Thus, the total number of vertices is 18.
Problem 3: A simple graph contains 35 edges, four vertices of degree 5, five vertices of degree 4 and four vertices of degree 3. Find the number of vertices with degree 2.
Given
- Number of edges = 35
- Number of degree 5 vertices = 4
- Number of degree 4 vertices = 5
- Number of degree 3 vertices = 4
Let the number of degree 2 vertices be n.
By the Handshaking Theorem, the sum of degrees of all vertices equals 2 × number of edges.
Sum of degrees = (4 × 5) + (5 × 4) + (4 × 3) + (n × 2).
Therefore, 20 + 20 + 12 + 2n = 2 × 35.
So, 52 + 2n = 70.
Hence, 2n = 18.
Therefore, n = 9.
Thus, the number of degree 2 vertices is 9.
Problem 4: A graph has 24 edges and degree of each vertex is k, then which of the following is possible number of vertices?
(a) 20
(b) 15
(c) 10
(d) 8
Given
- Number of edges = 24
- Degree of each vertex = k
Let the number of vertices be n.
By the Handshaking Theorem, n × k = 2 × 24 = 48.
Therefore, k = 48 ÷ n.
Since k must be a non-negative integer (degree of a vertex), n must divide 48.
Check each option:
For n = 20, k = 48 ÷ 20 = 2.4 (not an integer) - not allowed.
For n = 15, k = 48 ÷ 15 = 3.2 (not an integer) - not allowed.
For n = 10, k = 48 ÷ 10 = 4.8 (not an integer) - not allowed.
For n = 8, k = 48 ÷ 8 = 6 (integer) - allowed.
Thus, option (d) 8 is correct.
Applications and Uses
- Networking: checking degree distributions in network graphs and verifying simple consistency conditions.
- Euler trails and circuits: the parity condition on odd-degree vertices is a standard step when testing for Eulerian paths.
- Graph construction and impossibility proofs: the lemma is often used to show certain degree sequences cannot exist.
- Combinatorics and counting arguments: provides quick checks when counting incidences between two classes (e.g., people and handshakes).
Summary
The Handshaking Theorem gives a simple but powerful relation between vertex degrees and edge count: the total of vertex degrees equals twice the number of edges. From this follows useful parity results and many practical checks used in graph algorithms and combinatorial reasoning.
