New answers tagged dag
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 ...
Top 50 recent answers are included
