Proving a relationship between minimum Perfect Matching and minimum Hamiltonian Cycle

Question

The question states:

Let n > 0 be an even integer and let G = (V,E) be the complete graph on n vertices. Each edge e ∈ E has a non-negative weight w(e) >= 0 such that the weights satisfy the triangle inequality (for all a, b, c ∈ V, w(ac) <= w(ab) + w(bc)). Prove that if M is a minimum-weight perfect matching and H is a minimum Hamiltonian cycle, then 2w(M) <= w(H).

Here's where I've gotten, in plain words: If we have a perfect matching of n vertices, then we have n/2 edges in a perfect matching, and n edges in a Hamiltonian cycle. To go from a perfect matching to a Hamiltonian cycle, we double the number of edges. If we assume that all edges have the same weight (let's say w = 1 for all e ∈ E) then it's trivial to show that 2w(M) <= w(H). I'm just missing something when it comes to showing that for edges of different weights. I know it should rely on the triangle inequality, and the fact that this is a complete graph (so we're deciding which edge to use to connect any 3 vertices) is important, but I'm not sure how the two go together. Can anyone offer any hints or ideas?

Answer 1

As a hit/idea, I'll get rid of the extraneous information in the problem. You actually don't need that the graph is complete (it just needs to be Hamiltonian), and you don't need that the weights satisfy the triangle inequality (technically, the weights don't need to be nonnegative, either, but this is more of a convention thing).

Another hint:

Furthermore, start with a minimum weight Hamiltonian cycle. There are two perfect matchings that you can get immediately from this cycle, and comparing these weights should give you your answer. (Let me know if you want to see more detail.)