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