Let G be a graph with 15 vertices and 40 edges such that eve

Let G be a graph with 15 vertices and 40 edges such that every vertex has degree 5 or 6. (A) How many vertices have degree 5? (B) How many vertices have degree 6?

Solution

Given there are 15 vertices, 40 edges. Every vertex has either 5 or 6 degree.

Assume, every vertex is extended to 3 of its immediate next nodes.

Like Node 1 is extended to Node 2, 3, 4.

Node 2 is extended to Node 3, 4, 5.

....

Node 12 is extended to Node 13, 14, 15.

Node 13 is extended to Node 14, 15, 1.

Node 14 is extended to Node 15, 1, 2.

Node 15 is extended to Node 1, 2, 3.

If that happened, each vertex will have a total of 3 outgoing nodes, and 3 incoming nodes, which means the degree of each node is 6.

But if this happens, it requires a total of 15 x 3 = 45 edges. But, as given, we have only 40 edges.

Randomly remove 5 edges. Removing each edge will reduce the degree of 2 nodes from 6 to 5.

Therefore, removing a total of 5 edges, will reduce the degree of 10 nodes from 6 to 5.

Hence to conclude, 5 nodes will have a degree of 6, and 10 nodes will have a degree of 6.

You can check this back, by using the formula: (10 * 5 + 5 * 6) / 2 = (50 + 30) / 2 = 80 / 2 = 40 edges is what it is given.

Therefore, to answer your questions:

A. The number of vertices with degree 5 are: 10.

B. The number of vertices with degree 6 are: 5.