edited by
5,172 views
19 votes
19 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$
edited by

6 Answers

Best answer
35 votes
35 votes

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

edited by
14 votes
14 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.$

9 votes
9 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
1 votes
1 votes

$\sum deg = 2e$

total degree is 1+2+3+4+5+6+7+x

it as given that "every pair of vertices are connected with at most one edge" which means graph is connected

28+x = 2e

by looking at option we can say x=4 because $\sum deg = even$

Hence , option (d) is correct.

Related questions

1 votes
1 votes
4 answers
1
go_editor asked May 23, 2016
996 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. Show that any finite simple graph has at least...