# topological sort equivalence

For a given acyclic graph $G$, a topological sort is an ordering $v_1, \dots, v_n$ of the vertices such that the arrows in the graph are all directed forward under that ordering.

Question: can all topological orders of a graph $G$ be obtained from a single ordering by iteratively swapping two vertices that are not connected by an edge?

Motivation. In a certain context I am trying to prove that all topological sorts of an acyclic graph are in fact "equivalent". I want to do this by comparing $v_1, \dots, v, v', \dots v_n$ and $v_1, \dots, v', v, \dots v_n$ where there is no edge between $v,v'$.

• What do you mean by "iteratively"? Do you mean a single swap, or do you mean a sequence of swaps with some terminating condition? – G. Bach Nov 9 '13 at 16:11
• @G.Bach I want to prove all topsorts equivalent, by showing that topsorts are equivalent if they differ only by a single swap. Thus, I want to know whether any two topsorts can be transformed into one another by applying a sequence of swaps. – Hendrik Jan Nov 9 '13 at 20:56
• This should be possible, and I think the way to go about it is this: take two incomparable (i.e. no edge between them) vertices $v_1$ and $v_2$ and let $V_1$ be the set of all vertices that need to come after $v_1$, and define $V_2$ analogously. To make a swap of $v_1$ and $v_2$ legal, you'll have to think about what to do with the vertices that are in the symmetric difference of $V_1$ and $V_2$ (i.e. the vertices that only depend on one of $v_1$ and $v_2$), and keep them arranged appropriately during the swapping. – G. Bach Nov 9 '13 at 21:15
• @HendrikJan the vertices you want to swap, must they be next to each-other in the sort-permutation? (ie. can you do $\text{swap}\left(v_i,v_j\right)$ with any $v_i,v_j$, or must it be $\text{swap}\left(v_i,v_{i+1}\right)$) – Realz Slaw Nov 12 '13 at 1:44
• @RealzSlaw Good point. My initial idea was to restrict to neighbour swaps, but perhaps that does not work. – Hendrik Jan Nov 12 '13 at 21:11

Let $\tau_1: x_1, x_2, \dots, x_n$ and $\tau_2: y_1, y_2, \dots, y_n$ be two topological orderings of the vertices of graph $G$. Our aim is to show that $\tau_1$ can be transformed into $\tau_2$ by a sequence of swaps, each changing the position of two vertices in the sequence, not connected to each other by an edge of $G$.
Starting from the beginning compare the vertices $x_i$ and $y_i$ and select the first pair that differs. For notational convenience we assume $x_1 \neq y_1$. As $y_1$ must occurs in $\tau_1$ we can find $x_j=y_1$, $j>1$. Thus vertices $x_1, \dots, x_{j-1}$ are all before $x_j=y_1$ in ordering $\tau_1$, but all after $y_1=x_j$ in ordering $\tau_2$. This implies there is no edge in $G$ (in either direction) from $x_j$ to each of $x_1, \dots, x_{j-1}$. Thus we can "legally" swap $x_j$ with each of $x_1, \dots, x_{j-1}$ to get it to the first position. We obtain $\tau'_1: x_j, x_1, \dots, x_{j-1}, x_{j+1}, \dots, x_n$ which has the same first element as $\tau_2$.