A Counterexample

Several of you have proposed algorithms for problems 2, 3 and 4 based on the following idea: (1) find a matching, (2) remove the matching from the graph, (3) continue after modifying the problem.



I claimed that that wouldn't work except for some very special cases (for example, in bipartite graphs this works for some versions of the problem). Here's a very simple example to show that you have to do something completely different. The figure on the left shows a graph whose edges are colored, thus forming a decomposition into three matchings. On the right is a partial coloring of the same graph, showing a single perfect matching. If your algorithm is based on the idea described above, there will be no way to prevent the first matching from being this one. The problem is that the remaining uncolored edges cannot be split into two matchings.



Hint for all of the questions 2, 3 and 4: change the problem! Reduce it to a single problem you do know how to solve, not to an iteration where you cannot control how the sequence of problems you're solving behaves.