610 views

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?

1. $3$
2. $0$
3. $5$
4. $4$
edited | 610 views
+2

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$.

answered by Veteran (114k points)
edited by
0
you mean given graph is disconnected ?
0
I donot think that will cause any problem
+3
@srestha : Added information from the question, that there must be even number of odd degree vertices

.According to question we already have even number of odd degree vertices i.e ${1,3,5,7}$

Hence,$A.{3}$ and  $B.{5}$ are eliminated.
0
yes right
+3
Adding to @sourav's comment-
"In any finite graph with at least two vertices, there must be two vertices with the same degree."
So option B also get eliminated.
0

How to find the value of $E?$

+2

bro, there is no need to calculate E, as we know that according to handshaking lemma, degree sum will always be even.

So here if we calculate degree sum = 1 + 2 +.......+ 7 = 28, as we can directly eliminate option A and C directly here because by adding 3 and to the degree sum, we will not get even.

option B can be eliminated in this way since there is one vertex of degree 7 here which means it is connected to every other vertex, which means a degree of the 8th vertex cannot be 0.

So correct degree is 4...

0

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

0
But as it is simple graph, it should have max edges = 8c2 i.e 28. right? then x should be 0 also.
0
no x can't be zero as it is given one of the is vertex degree of 7.
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
answered by Active (5k points)
0
it is not given in  the question that graph is connected

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.$

answered by Loyal (8.3k points)

+1 vote
1
2