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$

edited | 120 views
0
im getting option A

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
0
for option D : what if graph is disconnected ?

you cant form a spanning tree.
0
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.

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

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

This is the solution image :

by Active (1.6k points)
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)

2