Prove/disprove - reverse topological sort transpose graph

Question

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<v_j$ 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<v_i$, because now there's a path from $v_j$ to $v_i$, and if condition B held, then the order $v_j<v_i$ 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.

Answer 1

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$.