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'|&gt;|S|$, we reach a contradiction.

This is, of course, wrong, but I cannot find the error?
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$.



A set of constraints for which your kind of argument does work is known as a matroid. The greedy algorithm that you describe does work for matroids (and, more generally, for greedoids). Your set of constraints satisfies a weaker condition: it is 2-extendible, meaning that in order to add a new element (in this case, an edge), you need to throw out at most two existing elements. The greedy algorithm always gives a 2-approximation for such systems of constraints.