A vertex with the highest post order number lies in a source SCC

Lemma

Suppose we have a directed graph $G = (V,E)$ and $post: V \rightarrow \mathbb{N}$ be the result of running the DFS algorithm to find connected components in an undirected graph . Then the vertex with the largest post order number lies in a source strongly connected component in the strongly connected component graph .

# Proof

Let $S$ be the strongly connected component with the vertex of highest $post$ value.

Suppose some other strongly connected component $S'$ were to have an edge connecting to $S$ in the strongly connected component graph .

From the lemma , $S'$ has a vertex with higher post order than all vertices in $S$. This is a contradiction as $S$ contains the vertex with highest post order.

# A vertex with the highest post order number lies in a source SCC

# Proof