H4.

Question 3: (5 points) Let G 2 (V, E) be a graph with edge costs satisfying the triangle inequality. Let V' E V and both V and V' have an even number of vertices. Prove or disprove: The cost of a minimum cost perfect matching on V' is at most the cost of a minimum cost perfect matching on V. (Note: For a prove you would need to argue that this always holds. To disprove it, one counter example is enough.)