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

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