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:
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:
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?