Cross Edge and Back Edge when doing BFS

Question

I was asking to prove that

For any directed graph, when we perform BFS, for each cross edge $(u,v)$, there is some time when both vertices $u$ and $v$ appear in the queue. (In other words, we have a queue like this: $Q = \langle v_1,v_2,..u,..,v,..v_k \rangle$.)

However, when I draw some graph; I've encountered this example

If we perform BFS starts from $a$, then what is the edge of $(f,c)$? clearly, if what I was about to prove is correct, $f$ and $c$ will never appear in the queue at same time during the whole execution of BFS. So $(f,c)$ is not cross edge. Then what edge is this ? It can't be back edge; since $c.parent$ is $a$, and $f.parent$ is $e$. they aren't tree edge, nor forward edge.

So what I am asked to prove is not correct?

So I guess that the statement only holds for undirected graph?

Answer 1

Your statement for directed graphs is not true. Your graph in the OP is a counterexample. However, for undirected graphs it is true since if $(a,b)$ is a cross edge then the depth-difference between the vertices is at most 1, i.e. $depth(a) = depth(b)$ or $depth(a)+1 = depth(b)$. Using this fact, which is proved below, you can prove your statement.

Assume that at some point you have the following queue configuration: $$v_1, v_2,\dots, v_k,a,\dots, u_1,\dots u_m \text{ (leftmost leaves first)}$$ where $v_i$s and $a$ have the depth $d$ and $u_i$s have the depth greater than $d$. Since $(a,b)$ is a cross edge, $a$ and $b$ belong to different ancestral trees, i.e., one of the $v_i$s is an ancestor of $b$ i.e, $b$ must be discovered before we reach $a$. If their depth values are equal then $b$ has already been reached (discovered) and so they must be at the same time in the queue. Otherwise, their depth values differ by 1 and so $b$'s ancestor (parent) must be one of the $v_i$, say $v'$. This $v'$ is popped and extended before we reach $a$ and since $b$ is a descendant of $v'$, $b$ is pushed into the queue before $a$ is removed.

Thus in both cases $a$ and $b$ appear in the queue for some time during the execution of BFS.

---

Claim: In a breadth-first search of an undirected graph for each cross edge $(a,b)$ $$0 \leq depth(b)-depth(a) \leq 1$$ Proof: Assume that $depth(b)-depth(a) > 1$. Then $depth(b)$ is at least $depth(a) + 2$. But $(a,b) \in E$ (a cross-edge) and hence $depth(b) = depth(a)+1$, a contradiction (see the following figure).