Skip to main content
1 of 2
Ami
  • 141
  • 1
  • 4

prove that a hamiltonian DAG has a single topological sort

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.

Ami
  • 141
  • 1
  • 4