33,133 views
1 votes
1 votes
1. Suppose that G is a non-directed graph with 12 edges. Suppose that G has 6 vertices of degree 3 and the rest have degrees less than 3. The minimum number of vertices G can have?

a) 2 b) 0 c)1 d)3

I am getting 3..plz verify

1 Answer

3 votes
3 votes
Minimum No of vertices will be 9.

 Sum of degree of vetices = 2* edges

6*3 + K*v = 2*12 (Let there are rest v vertices each of degree K)

K*v = 24-18 = 6

K*v = 6

Now if degree of rest of the vertices is 2 then v = 3 and in total 9 vertices.

And if degree of rest of the vertices is 1 then v = 6 and in total 12 vertices.

Minimum vertices G can have 9.
edited by

Related questions

0 votes
0 votes
0 answers
1
Malusi asked Jan 12
89 views
Consider a weighted undirected graph with positive edge weights and let (u, v) be an edge in the graph. It is known that the shortest path from source vertex r to u hasw...
0 votes
0 votes
1 answer
3
Dknights asked Dec 12, 2023
354 views
which of the following statements is true:a complete graph is $(N-1)$ regulara $(N-1)$ regular is a complete graph
1 votes
1 votes
1 answer
4