What is the number of vertices in an undirected connected graph with 27 edges,…

Concept:

The Handshaking Lemma states that in any undirected graph, the sum of the degrees of all vertices equals twice the number of edges: sum of deg(v) = 2 x |E|. This holds because every edge contributes exactly 2 to the total degree count — one for each of its two endpoints.

Application:

1. The graph has 27 edges, so the sum of degrees of all vertices equals 2 x 27 = 54.

2. The six vertices of degree 2 contribute 6 x 2 = 12 to this sum.

3. The three vertices of degree 4 contribute 3 x 4 = 12 to this sum.

4. Let r be the number of remaining vertices, each of degree 3; they contribute 3r to the sum.

5. The total degree sum equation becomes 12 + 12 + 3r = 54.

6. Solving: 3r = 54 - 24 = 30, so r = 10.

7. The total number of vertices is 6 + 3 + r = 6 + 3 + 10 = 19.

Cross-check:

Substitute back: with 6 vertices of degree 2, 3 vertices of degree 4, and 10 vertices of degree 3 (19 vertices total), the degree sum is 6x2 + 3x4 + 10x3 = 12 + 12 + 30 = 54, which equals 2 x 27 as required — confirming the count independently.

Result:

The graph has 19 vertices.