# Using minimum cover to find maximum matching in bipartite

I was shown an algorithm in a test for using minimum vertex coverage in bipartite graph to find maximum edge matching. It made a lot of sense to me and I failed to come up with an example that proves it wrong, so I'd be happy if you could help me understand its correctness: • By a "coverage" do you mean a vertex cover? Feb 2 at 16:40
• @MishaLavrov yes, sorry if that wasn't clear Feb 2 at 16:41
• Do you know the "max-flow min-cut" theorem? Feb 2 at 16:43
• @BrianBorchers yes, and I'm aware of how to use it to find maximum matching. Feb 2 at 16:44
• I deleted the tag "covering-spaces". See en.wikipedia.org/wiki/Covering_space Feb 2 at 16:45

Kőnig's theorem tells us that the number of edges in a maximum matching of a bipartite graph is equal to the number of vertices in a minimum vertex cover.

This immediately highlights one suspicious feature of the algorithm: we are not adding edges to $$M$$ at the same rate as we are removing vertices from $$U$$. More precisely:

1. In step 1, we "use up" a single vertex of the vertex cover to add a single edge to the matching.
2. In step 2, we "use up" two vertices of the vertex cover to add a single edge to the matching.
3. In step 3, we throw away a vertex in the vertex cover without adding anything to the matching at all.

Therefore if step 2 or step 3 are ever used, then the size of $$M$$ at the end will be less than the size of $$U$$ at the beginning, and therefore by Kőnig's theorem the matching $$M$$ will not be optimal.

For a specific example, consider the following graph:

a  b  c     d  e  f
\ | / \   / \ | /
\|/   \ /   \|/
x     y     z


The only minimum vertex cover here is $$U = \{x,y,z\}$$. One way the algorithm could be conducted using $$U$$ is to:

• Begin by selecting $$x \in U$$, $$c \notin U$$, and applying step 1 of the algorithm, adding $$(x,c)$$ to the matching and removing $$x,c$$ from the graph.
• Then, select $$z \in U$$, $$d\notin U$$, and apply step 1 of the algorithm again, adding $$(z,d)$$ to the matching and removing $$z, d$$ from the graph.
• Then, we are stuck with nothing to do for $$y$$; we remove it from the graph using step 3 and stop.

This creates a matching of size $$2$$, but there are size-$$3$$ matchings such as $$\{(a,x), (c,y), (d,z)\}$$, so the algorithm's output is not optimal.