The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+5 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 (99.8k points)
edited by | 295 views

2 Answers

+11 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 (92k 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
+5 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 (4.8k points)

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

38,115 questions
45,622 answers
49,310 users