# Prove/disprove - reverse topological sort transpose graph

I need to prove or disprove the following statement:

"Let $$G$$ be a directed acyclic graph, and $$v_1v_2...v_k$$ a topological sort of $$G$$. Then $$v_kv_{k-1}...v_1$$ is a valid topological sort of the transposed graph $$G^T$$."

(The algorithm used is the one presented in CLRS 22.4)

I think the statement is correct.

My logic is that for every two vertices $$v_i,v_j$$ s.t $$v_i in the sorting of $$G$$, one of two conditions hold:

A) $$v_j$$ is a decedent of $$v_i$$ in $$G$$, so in every topological sort of $$G$$, $$v_i$$ will be before $$v_j$$ in the sort.

B) or there's no path from $$v_i$$ to $$v_j$$ or the contrary, so $$v_i$$ and $$v_j$$ can switch places in the sorting, depending on the order that the DFS run on $$G$$.

From here, if condition A held then in the sorting of $$G^T$$, $$v_j, because now there's a path from $$v_j$$ to $$v_i$$, and if condition B held, then the order $$v_j is valid for some topological sort of $$G^T$$. And so the sorting $$v_kv_{k-1}...v_1$$ is valid sort of $$G^T$$.

Something still doesn't feel right about this... would appreciate any help or comment.

• Are you able to edit the question to further clarify what is that something in "something still doesn't feel right about this"? I could spot a logical gap. Mar 28, 2019 at 12:31

## 1 Answer

A topological sort of a graph $$G$$ is an order $$\pi$$ such that if there is a directed path from $$x$$ to $$y$$ in $$G$$, then $$x$$ precedes $$y$$ in $$\pi$$.

Let us now show that $$\pi^R$$ is a topological sort of $$G^R$$. If there is a path from $$x$$ to $$y$$ in $$G^R$$ then there is a path from $$y$$ to $$x$$ in $$G$$, and so $$y$$ precedes $$x$$ in $$\pi$$, and so $$x$$ precedes $$y$$ in $$\pi^R$$.

• Is there a difference from what you stated to statement A i presented? i don't see any.. Mar 28, 2019 at 13:42
• My point is that you don’t need condition B at all. Mar 28, 2019 at 13:44
• got it, now i understand it's redundant. toda raba Mar 28, 2019 at 13:48