Let \(T_1\) be the depth-first search tree of \(G\), and \(T_2\) be the breadth-first search tree of \(G\). Below is a proof sketch that they fit the requirements.

\(T_1\): for each edge \((u, v)\) in \(G\), assume without loss of generality that vertex \(u\) is visited first. \(v\) would belong to \(u\)’s subtree, as \(v\) would inevitably be discovered while exploring from \(u\), therefore the condition has been fulfilled. This is also known as a Trémaux tree.

\(T_2\): Let \(d(u)\) be the distance of a vertex from the root; this is also the depth of the vertex in the BFS tree. For each edge \((u, v)\) in \(G \setminus T_2\), \(|d(u) - d(v)| \le 1\).

• if \(d(u) = d(v)\), neither can be the ancestor of the other.
• otherwise assume without loss of generality \(d(u) + 1 = d(v)\). If \(u\) is the ancestor of \(v\), it must be the direct parent of \(v\), which means \((u, v) \in T_2\), which is a contradiction. Therefore \(u\) isn’t an ancestor of \(v\).