The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
120 views

Consider an undirected graph with $n$ vertices, vertex $1$ has degree $1$,while each vertex $2,3,.............,n-1$ has degree $4$.The degree of vertex $n$ is unknown. Which of the following statement must be true?

  1.  Vertex $n$ has degree $1$
  2.  Graph is connected
  3. There is a path from vertex $1$ to vertex $n$
  4. Spanning tree will include edge connecting vertex $1$ and vertex $n$
in Graph Theory by Boss (46.6k points)
edited by | 120 views
0
im getting option A

3 Answers

0 votes
I think answer should be D because spanning tree will include all vertices of graph .

 Option A is wrong because vertex N must have odd degree but not neccessarly 1 . since in a graph no. of odd degree vertices must be even and in given graph  all have even except 1 . thats why

option B it is not fixed that graph  must be connected it may be a is connected .

Option C if graph is disconnected then there is no path ib between 1 And N .

Correct me if i am wrong ;?
by Active (1.3k points)
edited by
0
for option D : what if graph is disconnected ?

you cant form a spanning tree.
0
answer is (C)
0
Then there will be spanning forest but that forest must include edge from 1 and  n i respective spanning forest .

 

for option C what if  graph is disconnected ??
0

i think this is the graph with minimum number of vertices for the above question

0
Path is there from 1st vertex to 7th vertex obviously, but im not getting how could option A be incorrect, as nth vertex with more than degree .1. not possible.

please some1 verify it
0
remove vertex  7 and link 1 to 6 . then ?
0
Since in option D iit is talking about Spanning tree so graph is connected bcoz spanning tree is possible in only connected graph . Ryt ??
+1
yaa :). its the solution
0
Since in option D iit is talking about Spanning tree so graph is connected bcoz spanning tree is possible in only connected graph . Ryt ??
 

Yess

0
Then answer must be D.
0
in the above image, is it satisfying option D ?? No

that above image is satisfying option A & option C

and the image in answer is satisfying only option C.

So answer is option C.
0
option D is failing for image above in comments.
+2

option D should be wrong, and Option C should be right !

@Smishra95

Option C if graph is disconnected then there is no path ib between 1 And N .

graph may be disconnected., But the nth vertex should be connected to the component which is the 1st vertex is connected !

WHY ?

let there are r components.... let the 1st vertex connected component is C1.

We all know that each component is a sub-graph, means it is also a graph.

therefore C1 is also a graph... 1st vertex is odd degree vertex, then there should be exist one more odd degree ( in worst case ) ===> all vertices have 4 as degree ===> nth vertex should be connected to C1 only.

Therefore a path should be exist between them.

if you didn't get this try to draw a graph without nth vertex connecting to C1.

0

yeah........ Got it       thankyou....

 

Actualy i read that It spanning tree will include edge connecting A and edge connecting vertex N. But  it is talking about same edge which is connecting both the vertices 1 and n .

 

Thanks @Shaik Masthan

0
Nice question + nice answer
0 votes

This is the solution image :

 

by Active (1.6k points)
0 votes
how can option d is correct bro?if it is then option b must be true in all cases so option c is true.
by (23 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,896 questions
55,153 answers
190,576 comments
85,317 users