The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

+29 votes

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

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

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

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.

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 449
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,079 questions

45,571 answers

132,066 comments

49,040 users