The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 votes

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$
asked in Graph Theory by Veteran (112k points)
edited by | 525 views

2 Answers

+19 votes
Best answer

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$


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

answered by Veteran (107k points)
edited by
you mean given graph is disconnected ?
I donot think that will cause any problem
@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.
yes right
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.


How to find the value of $E?$


 Lakshman Patel RJIT 

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



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.
+7 votes
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 (5.1k points)
it is not given in  the question that graph is connected

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

47,139 questions
51,388 answers
66,700 users