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

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.

---

Short quick counter examples for options (A), (B), (C).
$\color{blue}{Blue}$ edges represent tree edges and $\color{red}{Red}$ edges represent back edges.

Picture (I) is a counter example to statements in (A),(C).
Picture (II) is counter example to statement in (B).

This leaves option (D) which is correct.

[Trying to get a vertex adjacent to $u$ and not lying in a cycle containing $u$ and its other neighbors, you shall get the intuition as to why it is not possible...

Trying to get a vertex $\color{green}{Y}$, such that it does not line on a cycle where $u$ and its neighbors lie [Figure (III)]. But in such a situation, $\color{green}{Y}$ must be discovered before $u$ is discovered, or else the edge $uy$ shall be traversed during DFS and $u$ shall not be a leaf. So situation should be as shown in Figure (IV) and clearly now $Y$ lies on a cycle where $u$ and its neighbors lie.

------------------------------------------------------------------------------------------------------

Note:

To be more specific, the diagram IV should be as shown in IV'. Otherwise, one might feel that during the discovery of $Y$ from $X$, why is $u$ not discovered through that]

]

---

could anyone please tell me how to think and approach to draw graphs and cover all possible cases written in question

Answer 1

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 2

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

Answer 3

 

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

start DFS traversal from b or f

Comments

how option B is wrong?? removal of d or c can disconnect f and b

Answer 4

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.