Let G = (V U,E) be a bipartite graph such that each edge e E has an associated weight w(e). A matching for G is a subset M E such that no two edges in M share a common vertex. The weight of M is w(M) = eM w(e).

A greedy algorithm for bipartite matching could start with an empty matching M, and then repeatedly add the largest weight edge that does not share a vertex with an edge already included in M

(a) Give an example edge weighted bipartite graph for which the above greedy algorithm will fail to find the maximum weight matching. (2 marks)

(b) For bipartite graphs in which all the edge weights are distinct and each is a power of 2 (i.e. each weight is 2i, for 0 i), prove that the above greedy algorithm always produces the maximum weight matching. (4 marks)