First, let's define some terms. A matching is a set of edges in a Graph that do not share vertices. A cover is a vertex set that touches every edge.

Next, let's examine a couple facts about matches and covers in bipartite graphs. The first fact is that |Matching| <= |Cover|. This can be proven by defining a one-to-one function f:Matching -> Cover. Suppose that there are two distinct edges (a and b) in the Matching. By the definition of a cover, at least one of the vertices incident to each edge is in the cover. If f(a) = f(b), then a and b share a common vertex. Thus, M isn't an actual matching. We have reached a contradiction. Thus, |Matching| <= |Cover|.

The second fact is that if the matching is maximal and the cover is minimal, then |Matching| = |Cover|. The proof for this is algorithmic. To explore this more, it is necessary to introduce an M-Augmenting path. An M-Augmenting path is a path where the end-point edges are unmatched, and every other edge is matched. Let a * mark a matched edge.

An M-Augmenting path looks like:

A -- B -*- C -- D

It has an interesting property. Take every unmatched edge and match it, and take every matched edge and unmatch it. The new path looks like:

A -*- B -- C -*- D

Notice that the new path is also a valid matching, as no matched edge shares a vertex. However, there is now an additional matched edge. This is the basis of the maximal matching algorithm.

Consider an initial matching in adjacency matrix form:

X/Y | 1 | 2 | 3 | 4 | 5 | A | 1 1* B | 1* 1 C | 1 1* D | 1 1

Here, the horizontal and vertical axes each represent a set of vertices in the bipartite graph.

The algorithm accepts an arbitrary initial matching, and returns the maximal matching. The first step is to iterate over each Y vertex (A, B, C, D) and create a forest containing Y vertices that aren't matched. The next step is, for each vertex in the forest, add the adjacent vertices from matched edges, so long as the vertices aren't already in the forest. Repeat the last step, except add adjacent, unmatched X vertices. This process repeats until no new vertices can be added to the tree. If there is an M-Augmenting path, use it to augment the matching, then create a new forest. This process continues until no more M-Augmenting paths can be created.

In Pseudo-Code:

boolean augmentMatching(Matching m) X <- m.X //the X vertex set Y <- m.Y //the Y vertex set forest <- new Tree[] lastVertices <- new Vertex[] findMatchedEdges <- false for each vertex in X if vertex is unmatched tree <- new Tree tree.root = vertex forest.add(tree) lastVertices.add(vertex) end if end for while lastVertices.length > 0 lastVertices = new Vertex[] //reset the vertex set foreach vertex v in lastVertices foreach adjacent vertex r in v AND Y if r is NOT in forest AND findMatchedEdges == isMatchedAdjacency(r, v) v.child = r lastVertices.add(r) end if end foreach end foreach findMatchedEdges = NOT findMatchedEdges end while augmentingPath <- forest.getAugmentingPath() //if there is no M-Augmenting Path if augmentingPath is NULL return end if foreach edge in augmentingPath if edge.isMatched() edge.unmatch() end if else edge.match() end else end augment(m) end function

Now, let's work through an example, given the Matching:

X/Y | 1 | 2 | 3 | 4 | 5 | 6 A | 1 1 1* B | 1 1* C | 1* 1 1 D | 1 1* E | 1 1 F | 1 1 1

The only unmatched Vertex in the X set are E and F, so those are the only vertices in the forest.

Next, let's find the Y vertices that are adjacent to E and F. Note that the edges will be unmatched, but the vertices have matched edges. So the forest looks like:

E F / \ | 1 6 5

Next, let's find the matched edges of 1, 6, and 5 and add them to the tree. The vertices will be in the X set and cannot already be in the tree. The updated forest looks like:

E F / \ | 1 6 5 * * * A D B

This process repeats, until the forest is flushed out to:

E F / \ | 1 6 5 * * * A D B / \ 2 3 * C

The only M-Augmenting path is E -- 1 -*- A --3. Inverting that increases the matching to, though the new path: E -*- 1 -- A -*- 3.

X/Y | 1 | 2 | 3 | 4 | 5 | 6 A | 1 1 1* B | 1 1* C | 1* 1 1 D | 1 1* E | 1* 1 F | 1 1 1

Running the algorithm again gives the forest:

F / | \ 1 5 6 * * * E B D

Thus, there are no additional M-Augmenting Paths, so the algorithm is complete. This means the maximal matching is as follows: {E1, C2, A3, B5, D6}. The minimal cover must also have 5 elements. The formula for the minimum cover is {Unmatched X Verices} + {Found Y Vertices}. So the found Y in the last forest were {1, 5, 6} and {A, C} were the unfound X vertices. So the minimal cover is {A, C, 1, 5, 6}.