The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+38 votes
3.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$
asked in Algorithms by Active (3.7k points)
edited by | 3.3k views
0
Please someone explain why C is not answer?
0
@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?
+8

first one eliminate option C.

second one eliminate option B.

+6

Aayushi Aggarwal  

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 :)

+1
Before looking at answer try to find answer using proof via contradiction or counterexample.

6 Answers

+29 votes
Best answer

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

answered by Boss (10.7k points)
edited by
0
@Bikram sir, Please verify.
+6

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

0
@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.
+4
@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...
+11 votes

Consider following graph

Dfs is .

so D is answer.
 

answered by (89 points)
+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.
+9 votes
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.
answered by Active (3.2k points)
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.
+7 votes

By option Elimination :-

answered by Boss (22.7k points)
edited by
+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.
+5 votes

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

answered by Veteran (60.4k points)
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 ??

PLease explain ??

+1

MANSINGH HANSDA  

  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 :)
 

+2 votes
 

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

start DFS traversal from b or f

answered by Active (1.2k points)
+2
how option B is wrong?? removal of d or c can disconnect f and b


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

38,079 questions
45,571 answers
132,066 comments
49,040 users