The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+13 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$
in Graph Theory by Veteran (98.3k points)
edited by | 664 views

3 Answers

+23 votes
Best answer

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


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

by Veteran (113k 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.
+8 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
by Active (4.9k points)
it is not given in  the question that graph is connected
+2 votes

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

by Boss (17.2k points)

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
49,807 questions
54,727 answers
79,843 users