Determining the Number of Vertices in a Graph: A Step-by-Step Guide Using the Handshaking Lemma

In graph theory, one of the fundamental concepts is the relationship between the degrees of vertices and the number of edges in a graph. This relationship is captured by the Handshaking Lemma, which states that the sum of the degrees of all vertices in a graph is equal to twice the number of edges. Let's explore how to apply this lemma to a specific problem.

The Problem

Suppose a connected graph has 17 edges, 1 vertex of degree 2, 2 vertices of degree 3, 3 vertices of degree 4, and all other vertices of degree 7. How many vertices does the graph have?

Step-by-Step Solution

Step 1: Calculate the Sum of the Degrees

According to the Handshaking Lemma:

sum(degree) 2 × number of edges

In this case:

sum(degree) 2 × 17 34

The degrees of the vertices are as follows:

1 vertex of degree 2 2 vertices of degree 3 3 vertices of degree 4 Remaining vertices of degree 7

Let x be the number of vertices of degree 7. The sum of the degrees can be expressed as:

1times;2 2times;3 3times;4 xtimes;7 34

Simplifying the known degrees:

2 6 12 7x 34

20 7x 34

Step 2: Solve for x

To solve for x, we rearrange the equation:

7x 34 - 20

7x 14

x 2

This means there are 2 vertices of degree 7.

Step 3: Calculate the Total Number of Vertices

The total number of vertices is the sum of all vertices we counted:

1 vertex of degree 2 2 vertices of degree 3 3 vertices of degree 4 2 vertices of degree 7

1 2 3 2 8

Conclusion

The graph has 8 vertices.

This simple calculation demonstrates the application of the Handshaking Lemma in solving graph theory problems.