How post order relates to strongly connected components

Lemma

Let be a directed graph with two strongly connected components and . Let be the result of running the DFS to find connected components in an undirected graph algorithm . If there exists and such that then

Proof

As and are separate strongly connected components with an edge in the strongly connected component graph. As the strongly connected component graph is a DAG there is not a path from to in .

During the fun of DFS to find connected components in an undirected graph we must visit either a vertex in or first.

Suppose we first visit a vertex . Here all will be visited by explore from and the algorithm will have to leave via before it can visit a vertex of . Therefore all vertices in will have lower post number than any vertex in .

Suppose instead we first visit a vertex . From this vertex we will explore the whole of and before exiting . Therefore all vertices in and will appear in a branch below in the DFS tree. This gives that ‘s post number is larger than that for all vertices . So as required.