GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 15

Question

Let $\mathrm{G}$ be a simple undirected graph on 8 vertices such that there is a vertex of degree 1 , a vertex of degree 2 , a vertex of degree 3 , a vertex of degree 4, a vertex of degree 5 , a vertex of degree 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex? (Select all that are possible)

• A. 0
• B. 3
• C. 4
• D. 8

Answer 1

Since $\mathrm{G}$ is a 8 vertex simple graph, so, maximum degree of any vertex can be 7 which eliminates option $D$;
And if some vertex has degree 7 then it is adjacent to every vertex, so, graph is connected which eliminates option A.
In any graph, the number of odd degree vertices is always even, so the remaining vertex cannot have an odd degree.

Comments

whatad question man,

---

e<=3v-6 putting v=8 we are getting e=18
sum of degree =2*e
then the degree of last vertex is coming 8.
bt we know by that the vertices should have at max degree=n-1 so why using e<=3v-6 i am getting 8?