# 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) $$<$$ 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.

• Welcome to Computer Science! If this exercise comes from an accessible source, please add a url or reference in the question. (Yeah, I know it might come from CLRS. But I could be wrong.) Please show how far you have got and where you got stuck and raise some specific question abou it, instead of just asking the community to do some exercise that is, I assume, designed for you to do. All above will motivate and help people help you faster and better. – John L. Nov 5 '18 at 13:35
• @Apass.Jack Thanks a lot for the guidance, that's quite helpful to keep in mind. I have edited my question to include the details that you requested. – danigo991 Nov 5 '18 at 16:17

• If pre($$u$$) < 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$$) < post($$u$$) and $$v$$ is in the subtree rooted at $$u$$.
• If pre($$v$$) < 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$$) < post($$v$$) and $$u$$ is in the subtree rooted at $$v$$.