266 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 | 266 views

We know, sum of degrees of all vertices $=2\times \text{no. of edges}$

Say no. of edges is $E$

Degree of last vertices is $x$

then,

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

$28+x =2\times E.$

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

But One vertex of degree $7$ means it connected to all other vertex

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

edited by
0
you mean given graph is disconnected ?
0
I donot think that will cause any problem
0
@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
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