22-1 Classifying edges by breadth-first search

A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first tree can also be used to classify the edges reachable from the source of the search into the same four categories.

a. Prove that in a breadth-first search of an undirected graph, the following properties hold:

  1. There are no back edges and no forward edges.
  2. For each tree edge $(u, v)$, we have $v.d = u.d + 1$.
  3. For each cross edge $(u, v)$, we have $v.d = u.d$ or $v.d = u.d + 1$.

b. Prove that in a breadth-first search of a directed graph, the following properties hold:

  1. There are no forward edges.
  2. For each tree edge $(u, v)$, we have $v.d = u.d + 1$.
  3. For each cross edge $(u, v)$, we have $v.d \le u.d + 1$.
  4. For each back edge $(u, v)$, we have $0 \le v.d \le u.d$.

a.

  1. If we found a back edge, this means that there are two vertices, one a descendant of the other, but there is already a path from the ancestor to the child that doesn’t involve moving up the tree. This is a contradiction since the only children in the bfs tree are those that are a single edge away, which means there cannot be any other paths to that child because that would make it more than a single edge away. To see that there are no forward edges, We do a similar procedure. A forward edge would mean that from a given vertex we notice it has a child that has already been processed, but this cannot happen because all children are only one edge away, and for it to of already been processed, it would need to have gone through some other vertex first.

  2. An edge is placed on the list to be processed if it goes to a vertex that has not yet been considered. This means that the path from that vertex to the root must be at least the distance from the current vertex plus $1$. It is also at most that since we can just take the path that consists of going to the current vertex and taking its path to the root.

  3. We know that a cross edge cannot be going to a depth more than one less, otherwise it would be used as a tree edge when we were processing that earlier element. It also cannot be going to a vertex of depth more than one more, because we wouldn’t of already processed a vertex that was that much further away from the root. Since the depths of the vertices in the cross edge cannot be more than one apart, the conclusion follows by possibly interchanging the roles of $u$ and $v$, which we can do because the edges are unordered.

b.

  1. To have a forward edge, we would need to have already processed a vertex using more than one edge, even though there is a path to it using a single edge. Since breadth first search always considers shorter paths first, this is not possible.

  2. Suppose that $(u, v)$ is a tree edge. Then, this means that there is a path from the root to $v$ of length $u.d + 1$ by just appending $(u, v)$ on to the path from the root to $u$. To see that there is no shorter path, we just note that we would of processed $v$ sooner, and so wouldn’t currently have a tree edge if there were.

  3. To see this, all we need to do is note that there is some path from the root to $v$ of length $u.d + 1$ obtained by appending $(u, v)$ to $v.d$. Since there is a path of that length, it serves as an upper bound on the minimum length of all such paths from the root to $v$.

  4. It is trivial that $0 \le v.d$, since it is impossible to have a path from the root to $v$ of negative length. The more interesting inequality is $v.d \le u.d$. We know that there is some path from $v$ to $u$, consisting of tree edges, this is the defining property of $(u, v)$ being a back edge. This means that is $v, v_1, v_2, \dots, v_k, u$ is this path (it is unique because the tree edges form a tree). Then, we have that $u.d = v_k.d + 1 = v_{k − 1}.d + 2 = \cdots = v_1.d + k = v.d + k + 1$. So, we have that $u.d > v.d$. In fact, we just showed that we have the stronger conclusion, that $0 \le v.d < u.d$.