Suppose a simple graph has 18 edges,4 vertices of degree 3,and all other of degree 4.How many vertices does the graph have?

1

1 Answers

Oddman Profile
Oddman answered
A simple graph has no edges connected from a node to itself, so the total of the degrees of all the vertices involved will be 2*18 = 36. The total of the degrees of the degree 3 vertices is 12, so the total of the degrees of the degree 4 vertices must be 36 - 12 = 24. There must be 24/4 = 6 vertices of degree 4, making a total of 10 vertices in the graph.

You can construct such a graph as follows. Identify the vertices with numbers 1 through 10. Make the following connections:
(1-2-3-4-5-6-7-8-9-10-1)
(2-4)
(7-9)
(1-5-8-1)
(3-6-10-3)
Vertices 2, 4, 7, 9 will have degree 3. The remainder have degree 4. (There are many other possibilities.)

Answer Question

Anonymous