The strongly connected component graph is a DAG

Lemma

The strongly connected component graph is a DAG.

Proof

Let be directed graph.

Suppose two strongly connected components and in had paths connecting to and connecting to .

As and are strongly connected components we know there are paths , connecting to and vice versa as well as to .

However, connects to and connects to giving is not maximal. Therefore no such set of paths and exist.

Therefore no cycle can exist in the strongly connected component graph either.