0
$\begingroup$

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 neighbors in $G$.

My attempt :

  1. Need not be.
  2. Need not be.
  3. Need not be.
  4. seems true, but I've got confuse.

Can you explain for each option please?

$\endgroup$

1 Answer 1

1
$\begingroup$

To show that one of the statements is not true it suffices to give an example for which the statement is false. In the following example graphs the DFS is always started at node $s$ and the orientation of the edges indicates the search direction. Edges that are not oriented are not traversed during the search.

For statements 1. and 3. consider the following graph.

enter image description here

Both, $u$ and $v$, are leafs of the search tree. However, there is no node adjacent to both nodes in the original graph and there is no cycle containing $u$ and $v$.

For statement 2. consider the following graph.

enter image description here

No matter which node is removed from this graph, $u$ and $v$ are still connected.

For statement 4. (which is indeed true), an example will not suffice but a proof is required.

Claim: There is a cycle in $G$ containing $u$ and all its neighbors.

Proof: Let $s$ be the node at which the DFS was started. Denote by $P(u,s)$ the nodes contained in the path from $u$ to $s$ in the search tree. Call these nodes the predecessors of $u$. Assume that there is a neighbor $w$ of $u$ which is not contained in this set. This is only possible if $w$ is considered after $u$ in the DFS (otherwise, $u$ will be considered after $w$ and will thus be a successor of $w$). But then $u$ cannot be a leaf because $w$ is a neighbor of $u$ which has not yet been visited by the DFS. Thus, all neighbors of $u$ are contained in $P(u,s)$. Let $w$ be the neighbor of $u$ which is closest to $s$ in the search tree. Then $P(w,u) \cup \{(u,w)\}$ is a cycle in $G$ containing all neighbors of $u$.

$\endgroup$
1
  • $\begingroup$ Thanks for very very nice explanation. Beautiful explanation :) $\endgroup$ Nov 25, 2015 at 9:40

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .