If there is no Hamiltonian path in a DAG then there are at least two different Topological sorts

Question

I understand the concept that if there is no Hamiltonian path so there will be 2 smaller paths and with them I can build more then one topological sort but I am not sure how make it formal.

Can you help me to structure the proof?

Answer 1

Let's call two vertices $u$ and $v$ comparable if there is an oriented path from $u$ to $v$ or from $v$ to $u$, and call them incomparable otherwise. Now let's prove that if there is no Hamiltonian path in DAG then there exist two incomparable vertices. Let's use a proof by contradiction and prove instead that if all vertices in a given DAG are pairwise comparable then there exists a Hamiltonian path. Let's prove it by induction by a number of vertices. Obviously, this statement is true for $1$ and $2$ vertex DAGs. Not let's consider an arbitrary DAG where all vertices are pairwise comparable. There is exactly one vertex with zero in-degree in such graph. Let's call this zero in-degree vertex $a$. What is more, if you remove vertex $a$ from your DAG, the remaining subgraph will also be a DAG where every two vertices are comparable. By induction assumption you can build a Hamiltonian path $P$ in this subgraph. Let's call the first vertex of this Hamiltonian path $v$. Then there is an edge $(a, v)$ in the original DAG. Indeed, let's assume that such edge does not exist. But we know that there is a path from $a$ to $v$ (because they are comparable and there is no in-edges to $a$). Let $b$ be the second vertex of the path from $a$ to $v$. Then there is a path from $b$ to $v$, but there is also a path from $v$ to $b$ (by construction of $v$). Hence, there is a cycle in a considered graph. Contradiction. So there is an edge $(a, v)$ and $v$ is a start vertex of some Hamiltonian path $P$ in the subgraph without $a$. Thus $\{a\} \cup P$ is a Hamiltionian path in the original graph.

So in every DAG without a Hamiltonian path there is at least 2 incomparable vertices. Thus you can get two different topological sortings just by swapping the numerations on dfs subtrees of these two vertices.