# Is topological sort of an original graph same as post-ordering dfs of its transpose graph

I have an intuition that topo-sort of an original graph

 A -> B -> C
D -> B


topo-sort is [D, A, B, C] or [A, D, B, C]

If I transpose the graph

  C -> B -> A
B -> D


the postordering dfs of this transposed graph also gives [D, A, B, C] or [A, D, B, C]

Please, I can't mathematically prove/disprove it. If not true, an counter example would helpful.

A postordering is a list of the vertices in the order that they were last visited by the algorithm

https://en.wikipedia.org/wiki/Depth-first_search

• Try your claim on your transposed graph, and see if it still makes sense. – Yuval Filmus Apr 25 '20 at 9:08
• Hi @Yuval Filmus. I showed an example of the transposed graph in the question. I have tried several others, my claim seems to be correct based on my limited cases I tried. I can't find an counter example, and I am not capable of prove it mathematically – wenchao jiang Apr 25 '20 at 9:14
• I was suggesting to try your claim not on the graph you give, but on its transposition. – Yuval Filmus Apr 25 '20 at 9:15
• I try as you suggested. The claim still hold, the topo and dfs order are [C B A D, C B D A]. Do I miss anything? – wenchao jiang Apr 25 '20 at 9:25
• Please update your question to explain what you're doing. We cannot guess your mind. It's even better if you explain what you mean by "post-order DFS", since I've never heard this term. – Yuval Filmus Apr 25 '20 at 9:33

Let $$G$$ be a graph and $$G'$$ be it's transposed version. Your property follows from the following two facts:
1) The order in which vertices are visited by a postorder visit on $$G'$$ is the reverse of a topological order $$\sigma'$$ for $$G'$$ (in fact, that's a standard way to compute a topological order). You can see that this is true by noticing that if $$(u,v) \in G'$$ then $$v$$ must be visited before $$u$$ can be visited, i.e., $$v$$ follows $$u$$ in $$\sigma'$$.
2) If $$\sigma'$$ is a topological order for $$G'$$, then the linear order $$\sigma$$ obtained by reversing $$\sigma'$$ is a topological order for $$G$$. You can see that this is true because, for every edge $$(u,v)$$ of $$G$$, $$G'$$ contains $$(v,u)$$ and therefore $$v$$ precedes $$u$$ in $$\sigma'$$. This means that $$(u,v) \in G \implies u$$ precedes $$v$$ in $$\sigma$$.