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

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?

• Conversely, if there are at least two different topological sorts, then there is no Hamiltonian path. So, for a DAG, the uniqueness of a topological sort is equivalent to the existence of a Hamiltonian path (which must be unique). May 8, 2023 at 0:13

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.