# Comparing locally maximal and localy minimal Hamiltonian paths [closed]

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?

• What did you try and where did you get stuck?
– Juho
Mar 5, 2019 at 14:35
• I am stuck with a formal proof of this. Mar 5, 2019 at 14:39
• OK. How did you start the proof attempt?
– Juho
Mar 5, 2019 at 14:41
• @arielb Basically, you're just saying "Here's my homework. I can't do it. Please help me." Without knowing what you're stuck with, the only way we can help is to give you a full solution, but we're not going to do that -- it's your homework, not ours. Mar 5, 2019 at 14:50
• I tried with induction, for k=3 , the condition is fulfilled. We assume that w(H)>=w(h) for a Hamiltonian path with size n-1 and try to prove it for a Hamiltonian path with size n. Mar 5, 2019 at 14:55