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?