# Prove the following claim on Hamilton Path?

I am trying to prove the following claim:

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

1. Do topologic sorting.
2. 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:

• Base case is simple for n==0.

• Assuming claim is correct for n I want to prove for n+1

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:

1. 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.

2. 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. Apr 24 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.) Apr 24 at 4:58

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?

• 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. Apr 23 at 19:53
• Can you find a path between the two nodes? Since they are parallel in the topological sorting, what does that mean? Apr 23 at 19:55
• Also notice that the topological sorting is a DAG. Try to use this fact in your proof Apr 23 at 19:55
• there can never be a path connecting them if there is no direct edge. נכון? Apr 23 at 20:07
• And what would that mean about a hamilton path? a hamilton path must always go through all nodes Apr 23 at 20:08