Prove the following claim on Hamilton Path?

Question

I am trying to prove the following claim:

Given DAG graph, there is Hamilton path iff the following algorithm returns true:

Do topologic sorting.
Move on the graph's vertices one by one (from low to high). In case there is no edge connecting 2 vertices with adjacent values from the topologic sorting then return false. if no false was returned after we check all vertices, return true.

I am stuck of proving one side which is: if there is Hamilton path then the algorithm returns true.

I tried using induction on number of vertices in the graph n:

So I said, let's exclude the last vertex in the given Hamilton path (let's call it a), and assume by contradiction that the algorithm returned false.

This means one of the 2:

Two vertices with adjacent values had no edge connecting them and both aren't a. this contradictc the assumtion that the claim hold for graph with n vertices.
One of the two vertices is a and the other isn't a.

I am stuck on proving that case (2) will give us a contradiction, How may I continue?

To show (1), you first need to show that topological ordering "respects" vertex deletion -- that is, that if $v_{\rho(1)}, \dots, v_{\rho(k-1)}, v_{\rho(k)}, v_{\rho(k+1)}, \dots, v_{\rho(|V|)}$ is a valid TO for $G$, then $v_{\rho(1)}, \dots, v_{\rho(k-1)}, v_{\rho(k+1)}, \dots, v_{\rho(|V|)}$ is a valid TO for $G \setminus \{v_{\rho(k)}\}$. Then you can construct a failing TO for $G \setminus \{a\}$ from the failing TO for $G$ that you have assumed exists. Finally, because the IH holds for all possible TOs of an $n$-vertex graph (I suggest making this explicit), you get your contradiction. — j_random_hacker, Commented Apr 24, 2021 at 4:20
For (2), a useful property is that if there is a directed path from $u$ to $v$, $v$ must appear after $u$ in every TO. This should help you constrain the position of $a$ within the TO. Then show (e.g., via induction) that every TO of a HP-having DAG positions the HP's last vertex last in the TO. (Actually, strengthening the IH of this induction to "HP in $n$-vertex DAG $\implies$ TO contains all vertices in HP order with arcs between adjacent vertices" makes it no more difficult and will lead to a simpler direct proof overall.) — j_random_hacker, Commented Apr 24, 2021 at 4:58

nir shahar · Accepted Answer · 2021-04-23 19:46:56Z

0

Try to prove instead (without induction) that if the algorithm returned false, there is no hamilton path.

Hint: there must be two parallel nodes. Can we reach one from the other?

answered Apr 23, 2021 at 19:46

nir shahar

11.6k3 gold badges16 silver badges35 bronze badges

$\begingroup$ your suggestion is even harder, the algorithm returns false if there are 2 adjacent vertices such that there is no edge connecting them I don't see a way from here to prove that this means there is no Hamilton path. $\endgroup$
– daniel
Commented Apr 23, 2021 at 19:53
$\begingroup$ Can you find a path between the two nodes? Since they are parallel in the topological sorting, what does that mean? $\endgroup$
– nir shahar
Commented Apr 23, 2021 at 19:55
$\begingroup$ Also notice that the topological sorting is a DAG. Try to use this fact in your proof $\endgroup$
– nir shahar
Commented Apr 23, 2021 at 19:55
$\begingroup$ there can never be a path connecting them if there is no direct edge. נכון? $\endgroup$
– daniel
Commented Apr 23, 2021 at 20:07
$\begingroup$ And what would that mean about a hamilton path? a hamilton path must always go through all nodes $\endgroup$
– nir shahar
Commented Apr 23, 2021 at 20:08

| Show 2 more comments

1 Answer 1