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.
Prove that a hamiltonian DAG has a single topological sort
algorithms;graphs;graph theory;search algorithms;hamiltonian path