Search code examples
graph-theorydepth-first-searchdirected-acyclic-graphstopological-sorthamiltonian-path

Why does the existence of a Hamilton path in a Directed Acyclic Graph (DAG) show there is single way to topologically order the DAG?


Here is my understanding- we can find a Hamilton path by topologically sorting a DAG and checking if an edge exists between each vertex in this sorted order. And that somehow this shows that this topological order is the only one that can exist. How does showing that there is an edge between each vertex in the topological order indicate that this could be the only topological order?


Solution

  • The Hamiltonian path is one topological ordering T; suppose for contradiction that there was a different topological ordering T'. Then, look at the first point where T and T' disagree: suppose the i'th node in T is x and the i'th node in T' is y, for some i >= 0 with x != y.

    Then x comes before y in the first ordering T, but y comes before x in the second ordering T'. Since T is also a Hamiltonian path, there is a subpath of edges from x to y in the original DAG. At least one of these edges must be a backwards-edge in T', since the overall subpath leads backwards from x to y. This contradicts the definition of a topological ordering, so T' cannot have existed.