The Handshaking Theorem in Graph Theory: Understanding Vertex Degrees and Edges

Learn about the Handshaking Theorem, a fundamental theorem in graph theory relating the sum of vertex degrees to the number of edges. This guide explains the theorem, its proof, and provides examples demonstrating its application in solving graph-related problems.

The Handshaking Theorem in Graph Theory

Statement of the Handshaking Theorem

The Handshaking Theorem (also known as the Sum of Degrees Theorem or Handshaking Lemma) states that in any graph, the sum of the degrees of all vertices is equal to twice the number of edges. This is because each edge connects two vertices, thus contributing 2 to the sum of the degrees.

Symbolically: Σv∈V deg(v) = 2|E|, where deg(v) is the degree of vertex v, V is the set of vertices, and E is the set of edges.

Consequences of the Handshaking Theorem

  • The sum of the degrees of all vertices in a graph is always an even number.
  • In any graph, the number of vertices with odd degrees must be even.

Examples Applying the Handshaking Theorem

Example 1: Finding the Number of Vertices

A graph has 24 edges, and each vertex has a degree of 4. How many vertices are there?

Solution: Let n be the number of vertices. Then n * 4 = 2 * 24 => n = 12.

Example 2: Graph with Mixed Vertex Degrees

A graph has 21 edges. Three vertices have a degree of 4; the rest have a degree of 2. How many vertices are there in total?

Solution: Let n be the total number of vertices. Then 3 * 4 + (n - 3) * 2 = 2 * 21 => n = 18.

Example 3: Graph with Multiple Degrees

A graph has 35 edges. Four vertices have degree 5, five have degree 4, and four have degree 3. How many vertices have degree 2?

Solution: Let n be the number of vertices with degree 2. Then 4*5 + 5*4 + 4*3 + n*2 = 2*35 => n = 9.

Example 4: Determining Possible Number of Vertices

A graph has 24 edges, and every vertex has the same degree k. Which of these is a possible number of vertices: 15, 20, 8, 10?

Solution: n * k = 2 * 24 => k = 48/n. Only n = 8 gives an integer value for k (k = 6).

Conclusion

The Handshaking Theorem is a fundamental result in graph theory, providing a simple yet powerful relationship between the degrees of vertices and the number of edges in a graph. It's a useful tool for analyzing graph properties.