1,011 views
5 votes
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?

   
   
 

(A) 3

 

(B) 0

 

(C) 5

 

(D) 4

2 Answers

2 votes
2 votes
1+2+3+4+5+6+7+x=even

28+x=even

So x is even. So option a,c eliminated.

Also, there is a vertex with degree 7. So x's degree cant be 0.

So option d is a possible value.
0 votes
0 votes

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 becausedeg=even

Hence , option (a) is correct.

Related questions

1 votes
1 votes
1 answer
1
0 votes
0 votes
1 answer
2
gagan55 asked Jun 30, 2023
177 views
Number of hamiltonian cycles for a graph K 5, 5( bipartite graph ) ??
3 votes
3 votes
0 answers
3
Kabir5454 asked Jan 2, 2023
427 views
Let $G=(V,E)$ where $V=\left \{ 1,2,3,4,.....,150\right \}$ and $(u,v) \in E$ if either $(u mod v) =0$ or $(v mod u)=0$.The Chromatic number of G is ?
0 votes
0 votes
0 answers
4