# How to mathematically prove that a topological ordering on a cyclic graph will topologically sort its Strongly Connected Components?

Let's have a standard topological ordering algorithm (from CLRS):

Topological_ordering(G)
foreach vertex v in V do
v.color = white

for each vertex v in V do
if v.color = white then
Stack = DFS(G, v, Stack)
return Stack

// DFS

DFS (G, v, Stack)
v.color = gray
for each u adjacent of v do
if u.color = white then
Stack = DFS(G, u, Stack)
v.color = black
Stack.push(v)
return Stack


Now let's apply this to a cyclic graph G.

We will not have a topological ordering of the vertices of G, but we shall have a topological ordering of the graph of the Strongly Connected Components

The graph of the Strongly Connnected Components derived from the graph G is a graph in which each SCC is represented by only one vertex (also called compressed SCC graph or supergraph)

## Example

For example let's look at this graph: https://imgur.com/a/0EXOxJt (sorry for the poor drawing skills). In green the SSC of this graph.

Applying the algorithm above, one possible stack configuration is:

head ----> 2 ; 3 ; 4 ; 5 ; 1 ; 6 , 8 ; 7 ; 9

As you can see the vertices of an SCC are "all together". In other words we cannot have in the stack $$v_1, v_2, v_3$$ where $$v_1 \in S_1 \land v_3 \in S_1$$ and $$v_2 \in S_2$$.

How to prove this mathematically? Thank you.

• You say "How to prove this mathematically?" - what do you want to prove? What does "this" refer to? Please provide in the question a precise mathematical statement that you are looking to prove. Then, show us what progress you've made on trying to prove it yourself. What textbooks have you consulted? I suspect what you're asking for is a standard fact that is already proven in good textbooks.
– D.W.
Dec 19 '21 at 8:22
• I don't think this will produce a topological ordering of the SCCs, since jothing is preventing the DFS from first leaving the current SCC and going to the next one - and afterwards to continue work on the current SCC. Also the example stack configuration you wrote cannot be achieved - one cannot have 4 immediately after 3 in the stack since they are not connected together in a direct edge. Dec 19 '21 at 14:48