1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you, "if there is no Hamiltonian path in DAG then there exist two incomparable vertices" that's what I was missed $\endgroup$ – Aviv Liberman Nov 8 '20 at 16:54
  • $\begingroup$ I think the IH needs to be slightly stronger -- that there exists a HP that begins at the unique indegree-0 vertex. Otherwise it's not clear that the indegree-0 vertex you remove can be attached to the HP that must exist in the rest of the graph. $\endgroup$ – j_random_hacker Nov 8 '20 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.