# Wrong proof about maximum matching

Given a bipartite graph $$G=(U,V,E)$$, find a maximum matching.

Algorithm G:

• Let $$S\gets\emptyset$$
• Mark all edges unmatched
• For $$i\gets1$$ to $$|E|$$
• If $$i$$ is unmatched
• $$S\gets S\cup\{i\}$$
• End If
• End For

Proposition: Algorithm G is optimal.

Proof: Feasibility is easy by induction. We prove that $$|S|$$ is maximum. By contradiction. Assume that there exists a set $$S'$$ of edges that has more edges than $$S$$. Since $$S$$ is maximal, then no edge could have been added to it without violating its feasibility. Thus, $$|S|$$ cannot be increased. Since $$|S'|>|S|$$, we reach a contradiction.

This is, of course, wrong, but I cannot find the error?

• Why don't you pick an example input where this gives the wrong answer, work through what the proof says should be true, and check whether it is actually true and what is the first stage where it isn't true? That should help you find which stage in the proof was faulty.
– D.W.
Nov 17 '19 at 7:33
• Additionally, since the algortihm does not define a sequence of edges, there is always a run of this algorithm that output an optimal matching. For example the one that first iterate over edges in a fixed maximum matching and then the rest of the edges. Therefore, if you find it hard to construct a bad-example it is because you are concentrating on a predefined mximum matching in your graph. Try to go with other sequence/enumeration of edges on the same graph and you will find why the algorithm does not work Nov 17 '19 at 10:29

Consider the path graph of length 3: $$x-y-z-w$$.
Take $$S$$ to be $$y-z$$, and $$S'$$ to be $$x-y,z-w$$.
There is a difference between a maximal matching and a maximum matching. A maximal matching is a matching that is not a proper subset of any other matching. Hence, it is not possible to add another edge to a maximal matching (we can say a maximal matching can't be augmented). A maximum matching is a matching of maximal cardinality. Every maximum matching is also a maximal matching, but the converse is not necessarily true. Your statement "$$|S|$$ cannot be increased" is not true. There can exist other matchings having larger size, and the correct version would be that "$$S$$ cannot be augmented".
For example, let $$G = (V,E)$$ be a bipartite graph with bipartition $$V=X \cup Y$$, vertex sets $$X = \{x_1,x_2\}, Y = \{y_1,y_2\}$$ and edge set $$\{x_1 y_1, x_1 y_2, x_2 y_1\}$$. A greedy algorithm that first chooses $$S = \{x_1 y_1\}$$ cannot augment $$S$$ because it is maximal. However, there exists another matching $$S' = \{x_1 y_2, x_2 y_1\}$$ which has a larger cardinality than $$S$$.
Note that if both the subsets $$S$$ and $$S'$$ are maximal and $$|S'| > |S|$$ (or just $$S \ne S'$$), then $$S$$ is not a subset of $$S'$$, and each subset contains an element not in the other subset.