The Gateway to Computer Science Excellence

+57 votes

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?

- There must exist a vertex $w$ adjacent to both $u$ and $ν$ in $G$
- There must exist a vertex $w$ whose removal disconnects $u$ and $ν$ in $G$
- There must exist a cycle in $G$ containing $u$ and $ν$
- There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$

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

+52 votes

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

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

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

So, is my thinking right or am I wrong

+46 votes

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

+15 votes

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

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

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.

+9 votes

+5 votes

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

+2 votes

0 votes

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.

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.

52,375 questions

60,553 answers

201,952 comments

95,374 users