Skip to main content
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user
Bumped by Community user

prove Prove that a hamiltonian DAG has a single topological sort

Source Link
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.