GATE CSE 2018 | Question: 30

Question

Let $G$ be a simple undirected graph. Let $T_D$ be a depth first search tree of $G$. Let $T_B$ be a breadth first search tree of $G$. Consider the following statements.

1. No edge of $G$ is a cross edge with respect to $T_D$. (A cross edge in $G$ is between two nodes neither of which is an ancestor of the other in $T_D$).
2. For every edge $(u, v)$ of $G$, if $u$ is at depth $i$ and $v$ is at depth $j$ in $T_B$, then $\mid i-j \mid =1$.

Which of the statements above must necessarily be true?

• A. I only
• B. II only
• C. Both I and II
• D. Neither I nor II

Comments

@chauhansunil20th can u plz explain a bit more in case of undirected graph for DFS and BFS both.

---

1. In undirected graph’s DFS there is no cross edge because, think if in given graph there is cross edge then in it’s DFS there is path in between both having cross edge so any one of them would be ancestor of one another for sure and if there is parent child relation (more general say ancestor) then it is not cross edge. 
2. I think this was asked in 2016 also, and the correct values are |v-u| = {0,1}

---

Cross edge is not possible in a Depth First Tree of Graph … as suppose we are reaching a vertex v from u via some other node let w (root of u and v) .Now let u to v there is a cross edge it indicates that we could have reached v directly from u i.e v is a adjacent node to u in G. But that is not possible in Depth first Traversal v can only be explored from u via w, if v was adjacent to u in G then it should have been a child of u in Depth First tree of G.

Answer 1

1. Undirected graph cant have cross edges in DFS forest. (Only directed graphs can have)  ( Hence I is True)
   (If you do not agree just try it with taking examples. You cant draw)
    
2. Just draw a triangle SAB. Source is S. Vertex A and B are at same level hence distance $1$.  So here $| i - j | = 0$.   (Hence II is false)

Hence answer is (A).

Anyway, II is simple to understand from the above explanation.
Those who did not get I, you may see Theorem $22.10$ in Cormen)

Comments

Oops sorry, the comment was about arguing that II is correct but I didn't really read that II talks about BFS and not DFS.

---

I am not really getting it. Can Someone take an example to prove the ans explaining both the points in the Question ?
Thanks in Advance

---

I will update in detail, with image.

---

@ Ahwan Could you pls comment the source/name of this book?

---

@Ahwan

in second statement, if we had less than or equal to instead of equality ,,i guess then 2nd option would have been correct , rt?

BFS on same graph yields a tree . And in any tree if there exist an edge (u,v) , then the difference between the level of u and v is always less  than or equal to 1.

Is my reasoning correct ??

---

Theorem 22.10

---

Please update your ANSWER....option D is the correct answer.

---

Try to understand it first, any way it was verified with official GATE keys. In fact all answers in GO.

---

This is not asked in the question but still : Backward Edge too not exist in the DFS of an Undirected Graph. (am I right ?)

---

How can the edge between A-B exist in BFT as per your example @Ahwan. Option ll seemed confusing to me . Are they talking about the graph G or BFT?? 

---

@Tuhin Dutta, its clearly mentioned in question that G is a graph and Tb is the breadth first search of tree. they are taking if there is one edge in G then difference of the depth of vertices of this edge in Tb will be 1. but this is not true in case of triangle as Ahwan shown in example.

 

@Dhiraj Raj, Only forward and cross edge doesn't exist in undirected DFT.

---

How can option 2 contain a triangle . because the definition of tree is - it is directed acyclic graph . if i is at depth 1 and j is also at depth 1 and their is an edge between them then that will form a cycle.

How is it possible?

Can someone please explain me.

---

@Ruchi Vora

Read the option II once again.

For every edge (u,v) of G.

It talks about graph G not Td or Tb, a graph can contain a cycle.

---

got it!

---

If 2^nd option is |i-j|<=1 then it is true..

---

So, basically neither BFS or DFS yield cross edges. So (I) is wrong anyways.

In (II) condition we can have edges in the graph which are at the same level in the corresponding BFS traversal.

Say, node 1 is parent and node 2 and 3 are its children. So in DFS we will have edges (1,2) and (1,3). Here node 2 and node 3 are at the same depth i.e. depth 1, they are 1 level below node 0, while node 0 is at 0 depth (it is start of traversal). thus depth(1)-depth(2)=1-1=0. Statement (II) says it can only be 1. Thus it is false.

---

@Vishma P Das No, you’re wrong. BFS traversal of both undirected and directed graph can have cross edges.

Answer 2

I think the answer should be (A)

Comments

Nice explanation bro. Good work.

Answer 3

Undirected graphs can't contain forward edges and cross edges since in those cases, edge $(v,u)$ would have already been traversed during DFS before we reach $u$ and try to visit $v$.

Let's say $(u,v)$ is an edge in $G$ and level of $u$ in $G$ is i. If we visit $u$ then after traversing every node of level $i$ we need to traverse node $v$. Because vertex $v$ is already in Queue so for next level traversal we need to visit $v$. That means $|d(v) − d(u)| \leq 1$.

Comments

yes , if it contains cross edges then it directly implies that the graph is disconnected but the graph given is connected(DFS tree)

---

What would happen if  we have only one edge in G? I believe this edge would be a cross edge according to the given definition.

Answer 4

I think none of these bcoz for bfs it can be zero and a graph can have cross edge

Comments

i solvedit by counter examples and found none of these option d