Hint 4.5.7.1.

This is harder than the previous three questions. Think about which “side” of the graph the Hamilton path would need to be on every other step.