Prove that a hamiltonian DAG has a single topological sort

Question

I've been straggling a little proving the argument "a hamiltonian directed acyclic graph has a single topological sort".

This is pretty much the idea of what I've come along:

• lets prove by contradiction. so lets assume a hamiltonian DAG has at least 2 topological sorts.
• If there're few topological sorts - it means one of the following options:
• either there're at least 2 vertices that aren't dependent. meaning both of these vertices could be with 0 in-degree. but it contradicts the fact that the graph is hamiltonian (there's a hamilton path in G)
• either there exists a vertex that splits to 2 branches. such that the neighboring vertices could appear in different order in the topological sort. but it contradicts that the graph is hamiltonian because in such a case - after choosing a branch, we won't be able to visit the vertices of the second branch. however if we do have this possibility, we have come to a cycle that ends in the vertex that split to 2 branches. (contradiction to the graph being a DAG)
• Finally we get contradiction to our assume - thus the original statement is correct.

Would appreciate your thoughts and suggestions about the idea of proof.

Answer 1

Let $G=(V,E)$ be a Hamiltonian DAG.

Since $G$ is Hamiltonian, there exists a path $p = [v_1, \ldots, v_n]$ where $\{v_1,\ldots, v_n\}=V$. By definition, $p$ is a topological ordering.

Note that $v_i$ must come after each of $v_1, \ldots, v_{i-1}$ in every topological ordering, since we have path $[v_j, \cdots, v_i]$ for each $j$ smaller than $i$. Likewise, $v_{i+1}, \ldots, v_n$ must come after $v_i$ in every topological ordering since $v_i$ has a path to each of those.

Hence $v_i$ occurs in position $i$ in every topological ordering, i.e. every topological ordering is equal to $p$.