GATE CSE 2006 | Question: 48

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$. which one of the following statements is true?

• A. There must exist a vertex $w$ adjacent to both $u$ and $ν$ in $G$
• B. There must exist a vertex $w$ whose removal disconnects $u$ and $ν$ in $G$
• C. There must exist a cycle in $G$ containing $u$ and $ν$
• D. There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$

Comments

Proof Ideas : https://gateoverflow.in/1824/gate-cse-2006-question-48?show=526175#a526175

---

1. The Core Concept: The "No-Cross-Edge" Rule

When you run DFS on an undirected graph, you are exploring as deep as possible along a path before backtracking. This splits the graph's edges into two categories:

1. Tree Edges: The edges you actually walk across to discover new vertices. These form the DFS Tree.

2. Back Edges: The edges left over in the graph that you didn't use because the vertex at the other end was already visited.

Here is the golden rule of DFS for undirected graphs:

📌 A back edge can only connect a vertex to its own ancestor (like a parent, grandparent, great-grandparent) in the tree. >

It can never jump sideways to a cousin or a completely different branch (no cross edges).

Why is this true?

Think about how DFS works. If there was a physical edge connecting two completely different branches, DFS would have used that edge to explore further before backtracking and starting the second branch. The fact that it didn't means one vertex had to be discovered while the other was still actively being explored—meaning one must be an ancestor of the other.

2. Solving the Question (Step-by-Step)

Let's look at the leaf vertex $u$ mentioned in the question:

• The problem says $u$ is a leaf in the DFS tree. Being a leaf means it has no children below it.

• The problem also says the degree of $u$ in the graph is at least 2.

• Because it's a leaf, it uses exactly 1 tree edge to connect upward to its parent.

• Since its total degree is at least 2, it must have at least one back edge coming out of it.

Now, let's look at where all the neighbors of $u$ must live.

Step 1: Where are $u$'s neighbors?

By the No-Cross-Edge rule, every single back edge from $u$ must go to one of its ancestors.

Therefore:

• Neighbor 1 is its parent in the tree.

• Neighbor 2, Neighbor 3, etc., must be ancestors (grandparent, great-grandparent, etc.) further up the tree.

Step 2: The Structure of Ancestors

In any tree, if you trace the ancestors of a vertex up to the root, they all lie on a single, straight, linear path. They don't branch out.

Let's visualize this linear path from the highest ancestor down to $u$:

$$\text{Highest Ancestor} \rightarrow \dots \rightarrow \text{Grandparent} \rightarrow \text{Parent} \rightarrow u$$

Every single neighbor of $u$ lives somewhere along this exact straight vertical line!

Step 3: Forming the Cycle (Why Option D is True)

Since all neighbors of $u$ are on this single vertical path, let's find the highest ancestor that is a neighbor of $u$. Let's call this vertex $A_{\text{highest}}$.

Because $A_{\text{highest}}$ is an ancestor, there is a direct tree-path running down from it, through every other neighbor (like the grandparent and parent), all the way to $u$:

$$A_{\text{highest}} \rightarrow \dots \rightarrow \text{Grandparent} \rightarrow \text{Parent} \rightarrow u$$

But wait! $A_{\text{highest}}$ is also a neighbor of $u$ via a back edge, which means there is a direct edge connecting $u$ straight back to $A_{\text{highest}}$:

$$u \rightarrow A_{\text{highest}}$$

If you glue these two paths together, you get a perfect loop (a cycle):

$$A_{\text{highest}} \rightarrow \dots \rightarrow \text{Grandparent} \rightarrow \text{Parent} \rightarrow u \rightarrow A_{\text{highest}}$$

Look closely at this loop:

1. It contains $u$.

2. It contains the parent, the grandparent, and every other ancestor that was connected to $u$.

Thus, this loop forms a cycle in $G$ that contains $u$ and ALL of its neighbors.

Why the other options fail (In Simple Terms)

• Option A says $u$ and $v$ must share a neighbor: Imagine a tree that splits at the very top (the root) into two long paths. If $u$ is at the bottom of the left path and $v$ is at the bottom of the right path, their back edges stay inside their own branches. They don't share any neighbors at all.

• Option B says removing a vertex $w$ must disconnect $u$ and $v$: If the graph is a simple ring (a cycle), you can remove any single vertex and the remaining vertices stay connected through the other side of the ring.

• Option C says there must be a cycle containing both $u$ and $v$: Because $u$ and $v$ are on totally separate branches and cannot pass edges sideways to each other, you cannot create a clean cycle that wraps around both of them without turning it into a tree-like structure.

Therefore, Option D is the absolute, mathematically guaranteed truth.

---

Can we just take Counterexample for each case and try to find the correct option ?

Answer 1

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

Comments

**This is the best solution **

---

This is a very strong requirement: it says every neighbour of u together with u all lie on one cycle. But you can easily make a graph where u has two different neighbours that are in different parts of the DFS tree (different ancestors or subtrees) so they are not all on a single cycle with u. The above two-triangle construction already shows neighbors of u need not lie with u on one common cycle. So D is false.

can anyone clarify this?

---

@pavansan

consider a dfs traversal : A $\rightarrow$ E $\rightarrow$ C$\rightarrow$ D$\rightarrow$ F $\rightarrow$B

$B$ and $F$ are leaf nodes, let $F$ be $U$ and $B$ be $V$

if there were no cycles of $U$ with its neighbour, let's say $e(C,D)$ in $G$, does not exists, then we would not be able to get a dfs tree which satisfies the requirement presented by the question 

my learning : never conclude with just 1 graph, try to cretae scenarios given in the options

Answer 2

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

Comments

@Abhishek tarpara  yes, and in the exam, it's more difficult to think of an example like this. 

---

how to prepare for such a situation

---

practice, try solving

https://gateoverflow.in/4208/gate-cse-2000-question-2-19

https://gateoverflow.in/732/gate-cse-2001-question-2-14

Answer 3

Consider following graph

Dfs is .

so D is answer.
 

Comments

How option B) wrong??

---

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

---

Yes,it is a directed graph. Question is about undirected graph.

Answer 4

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.

Comments

it will form a cycle, but how can you conclude it will include all it's neighbours from this statement ? please explain.

---

draw a diagram and try to understand.. when u is in cycle then the neighbors also part of that cycle.

---

@ahwan

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

---

Thank u sir. got it.

Answer 5

By option Elimination :-

Comments

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

---

@Nishant Thanks.Corrected. Now See the edited Version.

Answer 6

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

Comments

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

---

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

---

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