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?

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

0

Reset to default

Browse other questions tagged or ask your own question.