Pre-order traversal on a search tree
First note that #2 and #3 are saying the same thing. Next, notice that if u is an ancestor of v in T, then in a pre-order traversal, we see u before v, and therefore pre(u) &lt; pre(v). On the other hand, since T is a depth-first search tree (as opposed to an arbitrary tree) of the connected undirected graph G, and $(u,v) \in G-T$, we can deduce that pre(u)&lt;pre(v) results in u being an ancestor of v.

The following image, taken from Wikipedia, can help:



Preorder traversal sequence: F, B, A, D, C, E, G, I, H (root, left, right)

Postorder traversal sequence: A, C, E, D, B, H, I, G, F (left, right, root)