CMI2013-A-06

Question

A simple graph is one in which there are no self-loops and each pair of distinct vertices is connected by at most one edge. Let $G$ be a simple 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?

• A. $3$
• B. $0$
• C. $5$
• D. $4$

Comments

We can also use havel hakimi theorem.

https://www.google.com/url?sa=t&source=web&rct=j&url=https://m.youtube.com/watch%3Fv%3D07Q6N-WeaGM&ved=2ahUKEwio79jbsrXdAhUV6LwKHTO4AxMQt9IBMA96BAgJEEg&usg=AOvVaw2kiTltJAPNxzgHmFMHSjm3

Answer 1

Sum of degrees of all vertices in a graph $=2\times \text{no. of edges}$

Let number of edges be $E$ and the degree of last vertex be $x.$

Then,

$1+2+3+4+5+6+7+x=2\times E.$

$28+x =2\times E.$

Now, putting in options we get answer (B) $0$ or (D) $4$

But one vertex of degree $7$ means it is connected to all other vertices making degree $0$ impossible.

So, degree must be  (D) $4$.

Comments

Yeah

I got it the point

$\Rightarrow$The number of odd degree vertices is even in case of a finite graph.

So option $(A)$ and $(C)$ eliminated, right? (Because if I add a degree of last vertex $3$ or $5,$ number of odd degrees vertices are odd, which is false)

and option $(B)$ is also eliminated because one vertex has degree $7$, so last vertex degree cannot be $0$.

So the answer is $(D)$

Thank you

---

But as it is simple graph, it should have max edges = 8c2 i.e 28. right? then x should be 0 also.

---

no x can't be zero as it is given one of the is vertex degree of 7.

Answer 2

Using Havel Hakimi Theorem

 $ 7,6,5,4,3,2,1,x $

${\color{Red} \not{7} },5,4,3,2,1,0,(x-1) $

${\color{Red} \not{7} },{\color{Red} \not{5} },3,2,1,0,0,(x-2) $

${\color{Red} \not{7} } ,{\color{Red} \not{5} } ,{\color{Red} \not{3} } ,1,1,0,0,(x-3) $

${\color{Red} \not{7} } ,{\color{Red} \not{5} } ,{\color{Red} \not{3} },0,(x-4)$

$ x-4 =0 $

$\Rightarrow x=4.$

Answer 3

as we know that for simple graph we must have even no of odd  degree vertices

since already 4 odd vertices (as 1,3,5,7) is given so last vertex degree must be some even , so either it will be 0 or 4 , now since graph is connected given in question so vertex with degree 0 cant be possible so its answer will be 4

 

that is option d

Comments

it is not given in  the question that graph is connected

---

@Gurdeep Saini yes, it is not given, but you are told there is vertex of degree “7”,and we have 8 vertices in the graph, so vertex having 0 degree is out of game !

Answer 4

$\sum deg = 2e$

total degree is 1+2+3+4+5+6+7+x

it as given that "every pair of vertices are connected with at most one edge" which means graph is connected

28+x = 2e

by looking at option we can say x=4 because $\sum deg = even$

Hence , option (d) is correct.