edited by
20,909 views
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?

  1. There must exist a vertex $w$ adjacent to both $u$ and $ν$ in $G$
  2. There must exist a vertex $w$ whose removal disconnects $u$ and $ν$ in $G$
  3. There must exist a cycle in $G$ containing $u$ and $ν$
  4. There must exist a cycle in $G$ containing $u$ and all its neighbours in $G$
edited by

12 Answers

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

 

 

edited by
Answer:

Related questions

59 votes
59 votes
7 answers
2
Rucha Shelke asked Sep 16, 2014
31,356 views
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:QueueStackHeapB-Tree