Post numbers in DFS tree of an undirected graph How could you prove:
An edge (u,v) is part of an undirected graph G. If post(u) $&lt;$ post(v) (i.e. the post number of u is smaller than that of v) then it implies that v is an ancestor of u in the DFS tree.  

So far I have understood that it does in fact imply that so I need to prove this. I have thought of doing it by contradiction but not exactly sure how I would go about doing that.
You conclusion is correct.

Here is (the sketch of) a proof.


If pre($u$) &lt; pre($v$), the search must discover and finish $v$ before it finishes $u$, since $v$ is on $u$’s adjacency list. That is, post($v$) &lt; post($u$) and $v$ is in the subtree rooted at $u$.
If pre($v$) &lt; pre($u$), the search must discover and finish $u$ before it finishes $v$, since $u$ is on $v$’s adjacency list. That is, post($u$) &lt; post($v$) and $u$ is in the subtree rooted at $v$.