Let $K_n$ be a weighted complete graph on $n$ vertices. Two Hamiltonian paths are formed as follows. The first one, $H$, is formed by starting at an arbitrary vertex, and at each stage proceeding from the current location to the unvisited vertex maximizing the weight of the connecting edge. The second one, $h$, is formed similarly, except that at each stage one chooses the unvisited vertex minimizing the weight of the connecting edge. Prove that $w(H) \ge w(h)$.
I tried with induction. For $k=3$, the conclusion is fulfilled. We assume that $w(H)\ge w(h)$ for a Hamiltonian path with size $n-1$ and try to prove it for a Hamiltonian path with size $n$, where I got stuck. How can I go ahead with induction?