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 21.1k 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.