GATE CSE 2000 | Question: 2.19

Question

Let $G$ be an undirected graph. Consider a depth-first traversal of $G$, and let $T$ be the resulting depth-first search tree. Let $u$ be a vertex in $G$ and let $v$ be the first new (unvisited) vertex visited after visiting $u$ in the traversal. Which of the following statement is always true?

• A. $\{u, v\}$ must be an edge in $G$, and $u$ is a descendant of $v$ in $T$
• B. $\{u, v\}$ must be an edge in $G$, and $v$ is a descendant of $u$ in $T$
• C. If $\{u, v\}$ is not an edge in $G$ then $u$ is a leaf in $T$
• D. If $\{u, v\}$ is not an edge in $G$ then $u$ and $v$ must have the same parent in $T$

Comments

Let it be any theory question in Gate exam, make use of logical connectives to prove them True or False. It tells you which counter example to generate.

---

what will happen if i modify the last option instead of parent if i write ancestor then it will be correct or not?????

---

Yes correct

Answer 1

Let this be the DFS order of the tree, then,

$u= D$ and $v = F$

So, we conclude that

1. It is not necessary that there is an edge between them.
2. If there is no edge then $u$ must be leaf i.e. $D$ is leaf here.
3. It is not always possible that $u$ and $v$ have same parent. But they have same ancestor.

Correct Answer: $C$

Comments

How C can be always correct ...here is counter example....

---

@Ayushpal yes, I also thinking same, than how c is always correct? please anyone clarify.

---

Read the question carefully, option C says If (u,v) is not an edge in G, then u is a leaf in T

It is talking about u, not v

Answer 2

C is the correct answer..because it may happen that we read vertex u(leaf node) and hit a dead end and backtracking to vertex y(say) then searching for possibilites we read v ..so it is nt the case that u,v must have any descendant relationship .. You can try with random graphs and arrive at the same conclusion

Comments

What about the case when u-v is an edge then I guess still there may be a possibility that u is a leaf node since then even v will also be a leaf node and we can visit v after we have visited vertex u .

Answer 3

OptionA is wrong.

Option B.>{u,v} must be an edge; this statement made it false . else it may correct.

Now consider below img

Here as per question v is immediately visited after u.

If part is satisfied for option C & D in above img of resultant Depth first tree traversal

But then part is satisfied for option C only.

So C is the correct ans.

Answer 4

 

In DFS after visiting u, there is no child node then back tracking is happen and then visit the nodev. There is no need of (u,v) be an edge.