2
$\begingroup$

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?

$\endgroup$

closed as unclear what you're asking by David Richerby, Juho, Evil, Discrete lizard Mar 6 at 14:52

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ What did you try and where did you get stuck? $\endgroup$ – Juho Mar 5 at 14:35
  • $\begingroup$ I am stuck with a formal proof of this. $\endgroup$ – arielb Mar 5 at 14:39
  • 1
    $\begingroup$ OK. How did you start the proof attempt? $\endgroup$ – Juho Mar 5 at 14:41
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Mar 5 at 14:50
  • $\begingroup$ 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. $\endgroup$ – arielb Mar 5 at 14:55