Consider the following problem: we are given a graph G(V, E) with weights w : E R0. We want to find a closed walk of minimum cost that visits all edges (possibly, more than once). 1. Show that a solution of this problem can be deduced from a solution of the following: find a set of edges of minimum cost to be added to G, so that the resulting graph is Eulerian. 2. Show that the problem in part 1 can be reduced to a maximum weight matching problem. Conclude that the original problem can be solved in polynomial time. 2