Identifying a Maximum matching and a minimum cover for a specific bipartite graph

bipartite-graphsgraph theorymatching-theory

I have been given the following matching:
$$ M =\{ \{a,3\}, \{b,1\},\{d,4\},\{f,5\}, \{g,6\},\{h,7\},\{i,9\} \}$$
in the bipartite graph:
enter image description here
The matching looks like:
enter image description here

I applied the augmented path method to get the following 2 red edges, which we exchange for 1 green edge – that's a good deal!
enter image description here
Which gives a better matching of the form:
$$ M' =\{ \{a,3\}, \{b,2\},\{c, 1\}, \{d,4\},\{f,5\}, \{g,6\},\{h,7\},\{i,9\} \}$$

enter image description here

How do I know whether or not this matching is maximal? normally one gets a minimum vertex cover as a dual property of a maximum matching, how would one apply this to the current problem?

Edit:
I think my real question would be how do I find a minimum vertex cover to see if this matching is maximal (cardinality should be the same).

Best Answer

If you have a maximum matching, then you won't be able to find an augmenting path (of course) and the search for possible augmenting paths will produce a vertex cover.

For example, for your second matching (of size $8$) an augmenting path should:

  • start at one of the vertices $\{8,10\}$, which are not covered by the matching yet.
  • from there, go to one of their neighbors: $\{b, g, h\}$.
  • from there, take an edge of the matching, going to the corresponding vertex from $\{2,6,7\}$.
  • from there, go to one of their neighbors: of vertices we haven't seen yet, that's just $\{f\}$.
  • from there, take an edge of the matching, going to $\{5\}$.
  • from there, we're stuck, because no edges out of $5$ go to a new vertex we haven't seen before. There's no way to get to $e$ or $j$.

So this is a proof that there's no augmenting path. (Note: we could have done this search from the other direction, starting at the uncovered vertices $\{e,j\}$. Just checking one direction is enough, because any augmenting path would connect one of $\{8,10\}$ to one of $\{e,j\}$.)

We can use the search to find a minimum vertex cover, which is a more concise proof of optimality. Start with the vertices $\{b,f,g,h\}$, which cover all edges between vertices we've considered in our search. If we add in the vertices from the bottom part we haven't seen in our search - the vertices $\{1,3,4,9\}$ - then the resulting set $$ \{1, 3, 4, 9, b, f, g, h\} $$ is a vertex cover of the same size as the matching.

(In general, in a graph with bipartition $(A,B)$ if you start a search from the unmatched vertices on side $A$, and you don't find an augmenting path, you can find a minimum vertex cover by taking the vertices on side $B$ you do see, together with the vertices on side $A$ you don't see. There can't be an uncovered edge - which would go from a vertex on side $A$ you do see from a vertex on side $B$ you don't see - because then that vertex on side $B$ would become one of the ones you do explore.)

Related Question