90 votes 90 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$ Algorithms gatecse-2006 algorithms graph-algorithms normal + – Rucha Shelke asked Sep 26, 2014 edited Oct 25, 2017 by kenzou Rucha Shelke 20.9k views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments imShreyas commented Nov 7, 2019 reply Follow Share 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. 0 votes 0 votes HitechGa commented Dec 31, 2021 i edited by HitechGa Dec 31, 2021 reply Follow Share 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]] 5 votes 5 votes TheSourabh commented Nov 9, 2023 reply Follow Share could anyone please tell me how to think and approach to draw graphs and cover all possible cases written in question 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes clearly option a b and c are eliminated. The correct answer is d venkatn68 answered Aug 1, 2019 venkatn68 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes In a strongly connected component every two vertices must be reachable from one to other and it is maximal component. From given graph {P, Q, R, S, T, V} and {U} are strongly connected components. varunrajarathnam answered Aug 6, 2020 varunrajarathnam comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Suppose $u_1,u_2,u_3,….,u_n$ are neighbors of vertex u. Now when we run dfs then it is not possible that we reach $u$ before exploring all the neighbours of $u$ because then $u$ will have something to explore and then $u$ will not become a leaf in DFT. Suppose in DFS we reached $u_1$ through a vertex say $v$ then $u_1$ will explore all of its neighbour but it will not visit $u$ since other neighbours of $u$ are still remaining but it will not backtrack before exploring every other neighbours of $u$ since there is an edge from $u_1$ to $u$ and there is an edge from $u$ to its every neighbour. So the only possibility is that from $u_1$ we have some path to at least one of the neighbour of $u$ then only it will be possible for $u$ to be a leaf. If there is no path to at least one of the neighbour of $u$ then we must have visited $u$ and then $u$ will not become a leaf. Now suppose we have path from $u_1$ to $u_2$. Then after reaching $u_2$ we can claim that we must have path to some neighbour say $u_3$ of $u$ other than $u_1$ else we would have explored $u$ and then $u$ would not be able to become leaf as it has some neighbour which is not been explored by DFS. So we have now something like this $u_1$ some path to $u_2$ some path to $u_3$. And like $u_2$ we can claim the same for $u_3$. At last we will get $u_1$ some path to $u_2$ some path to $u_3$.….some path to $u_n$ and then only $u$ will be visited from $u_n$ via some path or direct edge . Also there is an edge from $u$ to $u_1$. Hence in original graph they will all be in a cycle. sameer_hack answered Jan 29, 2023 edited Jan 29, 2023 by sameer_hack sameer_hack comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Simplified the best answer graph ans D Ray Tomlinson answered Jul 27, 2023 Ray Tomlinson comment Share Follow See all 0 reply Please log in or register to add a comment.