7.3k views

Let $T$ be a depth first search tree in an undirected graph $G$. Vertices $u$ and $ν$ are leaves of this tree $T$. The degrees of both $u$ and $ν$ in $G$ are at least $2$. which one of the following statements is true?

1. There must exist a vertex $w$ adjacent to both $u$ and $ν$ in $G$
2. There must exist a vertex $w$ whose removal disconnects $u$ and $ν$ in $G$
3. There must exist a cycle in $G$ containing $u$ and $ν$
4. There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$

edited | 7.3k views
0
Please someone explain why C is not answer?
+1
@Arjun sir, i m getting answer B), plz help...
0
Is there a way to get the answer of this question without using counter examples?
+11

first one eliminate option C.

second one eliminate option B.

+6

Is there a way to get the answer of this question without using counter examples?

Yes possible. This question is straight forward.

It says Let T be a depth first search tree in an undirected graph G. Vertices u and ν are leaves of this tree T. The degrees of both u and ν in G are at least 2

That means :

G is original graph.

T is DFS Tree , where u and v are two leaves .

Both of u and v  have degree 2 only possible when G have a cycle with both u and v  .

Hence option D is only correct :)

+2
Before looking at answer try to find answer using proof via contradiction or counterexample.
+1
0
You need to look for the vertex that would disconnect the the two vertices u and v in the graph and not in the DFS tree.

One diagram, which is eliminating option A, B, C.
Hence D is the answer.

by
edited by
0
@Bikram sir, Please verify.
+12

@ahwan

yes, correct.

one point i want to add , it says in question

Let T be a depth first search tree in an undirected graph G. Vertices u and ν are leaves of this tree T. The degrees of both u and ν in G are at least 2

G is original graph.

T is DFS Tree , where u and v are two leaves .

Both of these leaves have degree 2 only possible when G have a cycle with both u and v  .

Option D is straight forward from this given statement.

+2
@Bikram sir, but we have to prove G have a cycle wih u & all it's neighbours. So how that statement proves anything about all of it's neighbours. I did not get it.
+8
@Ahwan

see, " The degrees of both u and ν in G are at least 2" this only possible when they form a cycle in G . Bcoz in DFs tree T u and v have degree 1 as they are leaves  .

And when u ( that leaf in T) have cycle , it's neighbours also part of that cycle , is not it ? Think again :)
0
Got it at last. Thank you sir @Bikram Sir.
0
@ahwan

in ur diagram V and U are not having degree atleast 2

which is mentioned in the question
0

@A_i_\$_h Check again. They have degree 2 each.

0
@ahwan yes sorry i was looking at the DFS tree instead of the graph...
0
Refer my answer if any confusion
0
But here leaves should have degree at least 2 and in above graph u and v doesn't have degree 2.

So, is my thinking right or am I wrong
0

@Pratik Kulkar

Sorry, but u r thinking it wrong

Because definition of degree is different for both graph and tree.In above graph u and v have degree 2.

0
C) cannot be answer. Because, G can have more than one cycle. rt??
0
+1
Done but it's very hard to find example..

Let T be a depth-first search tree in an undirected graph G. Vertices u and ν are leaves of this tree T. The degrees of both u and ν in G are at least 2.

Let's interpret question correctly and draw inferences

Vertices u and ν are leaves of this tree T.

Means (1) (u,v) is not an edge in the graph otherwise one would be have been descendent of another and both of them must not be leaves.

(2)If vertices u and v are leaves of tree T, then when DFS was exploring them, after exploring say vertex u, it was unable to find any new unvisited neighbour of u and hence, it had to backtrack the search.So u became leave of T. Same story goes with vertex v.

(3)If degrees of vertices u and v are at least 2 then I say consider the scenario for vertex u

Consider some intermediate vertices K and L which are neighbours of vertex U, and there may be more vertices than K and L, ahead of them connected to either one of them(to K or L) but for simplicity, I consider only two(K and L).

Now, say my DFS algorithm explored vertex K, coloured it, Grey, then it went to vertex U and found it WHITE (means unvisited) so it marks it Grey and makes the edge (K,U) a tree edge. Now DFS examines neighbour of U and finds neighbour L.

Now if the neighbour L was WHITE (Means not visited), DFS would have visited this vertex L and then edge (U,L) would have been marked as tree edge and in this case Vertex, U would no longer be a leave in DFS Tree T.

So, Necessarily my vertex L was visited before U (L Maybe GREY or BLACK in colour) and this would have been connected to vertex K via some other vertices or directly, otherwise, it was impossible for this vertex L to be discovered via path any other than from U to L.

So, what all this means?

Yes Vertex U and it's neighbour are in a cycle and your DFS will mark some edges as back edges.

The similar story would hold for vertex V.

So, even if Option had said

"Vertex U and V are involved in cycle with their neighbour" then also this would have been true.

So Option (D) is the answer.

+3
Great inferences drawn!! *_* This is the best logical answer :)
0
Perfect!!!
0
Great inference sir, it clears all the hidden story.

Thank you!
0
gr8 explantion....thanks
0
Best explanation :)

Consider following graph

Dfs is .

so D is answer.

+1
I think it is correct as rest of the cases have counter examples.
+6

@ Nikunj Vinchhi  D is the right answer, as the degree of node "u" is atleast 2 and it is a leaf node in DFT

and this is possible only when node u forms a cycle and it is visited last in the cycle.

0
@Marv can u plz gie counter examples for B and c
0

according to me this may be the counter example for options a,b,c

start DFS traversal from b or f

0
How option B) wrong??
+1
The Solution shown here contains Directed edge but question asked for undirected graph.

Also not provides counter for Option C as the given graph contains a cycle containing u(7) and v(5).

Correct Me @Anirudh
0
Yes,it is a directed graph. Question is about undirected graph.
I took many examples and didnt understand the question for half an hour.

But now i realise, on reading clearly. its very easy and direct.

A LEAF. in a DFS TREE. has degree two.
Another LEAF. in a DFS TREE. has degree two.

Both can be non adjacent leaves also.

It implies that if a LEAF has degree two then it will form a cycle.

Since it is non adjacent leaves that have cycle. so Option C may be wrong.

Hence option D.
0
it will form a cycle, but how can you conclude it will include all it's neighbours from this statement ? please explain.
+1
draw a diagram and try to understand.. when u is in cycle then the neighbors also part of that cycle.
0
@ahwan

Take that graph draw by Nikunj in his answer and see how u and it's neighbors form a cycle ..
0
Thank u sir. got it.

By option Elimination :-

edited
+1
@rajesh pradhan in second graph G option A is satisfied..here vertex x is adjacent to both u and v in G..correct by adding one more node(say y) between x and v..
0
@Nishant Thanks.Corrected. Now See the edited Version.

I also have doubt on this , may be helpful to remove some option .otherwise c,d is answer

0
@Anirudh I think instead of edge bu , edge uf should be there in the resultant Depth first Tree.
0

I still have a doubt in option D why in a graph there must be a cycle .

In your example only where is the cycle , its not necessary to have a cycle at 'U' with all its neighbours ??

+1
1. A LEAF. in a DFS TREE. has degree two.
2. Another LEAF. in a DFS TREE. has degree two.
3. Both are non adjacent leaves also.

It is only possible that a LEAF has degree two  in original graph when it  form a cycle.

so option D is only correct :)

according to me this may be the counter example for options a,b,c

start DFS traversal from b or f

+2
how option B is wrong?? removal of d or c can disconnect f and b
Here u and v are leaves in DFS tree. But u and v have degree >=2 in the original graph.

So now if u or v connects to some unvisited node in the graph, they wont be leaves in the DFS tree, so to have degree>=2 they should be connected to already some visited nodes, and hence u and v both will form cycle with their neighbors. But it is not necessary that they both are contained in the same cycle.
by