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.