Page 291 Exercise 4

Proving that a depth first spanning tree T has no cross edges relative to the graph G, is analogous to proving that T forms a tree.

First, for an undirected graph the proof is trivial since technically speaking the edges of an undirected graph are divided into only tree and back edges.  Thus, there are no cross edges in an undirected graph.

   
Second,   we note that with a digraph the edges are typically divided into four categories: Tree, Back, Forward, and Cross.  The diagram below shows a graph, with all four types of edges, that you may use as a reference.  The tree edges are <0,1> <1,2> <2,3> <3,4> <0,6>.  Edge <0,3> is forward.  Edge <3,1> is back, and edge <4,1> is cross.   

Cross edges are only conceptually distinct from back edges.  Technically, a cross edge, like a back edge, is defined as an edge in which the new vertex has a higher dfn (depth first search  number) than the previously visited vertex to which it is adjacent.  Cross edges are used to refer to edges that cross from right to left on the graph, any other edges with a higher dfn for the new vertex are back edges. 

The proof given in problem Page 292, Problem 12 demonstrates that the depth first search eliminates the back edges from a graph during the traversal.  Since cross edges are only conceptually distinct from back edges any traversal which eliminates back edges will also eliminate the cross edges.