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

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: The matching looks like:

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! 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\} \}$$

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).

• Do you know how to find a minimum vertex cover from a maximum matching? – Misha Lavrov Jan 15 at 19:26
• König tells me that "If G is bipartite, the cardinality of the maximum matching is equal to the cardinality of the minimum vertex cover." I know that a vertex cover is a set of vertices that are adjacent to every single edge in the graph AND I know that the augmenting path method terminates to give me a maximum matching - I'm just kind of stuck right now because every path I continue to use just leads nowhere. – Wesley Strik Jan 15 at 19:53
• So I know what a cover is, but I'm having trouble finding one. I think the answer to your question would be no. – Wesley Strik Jan 15 at 19:55
• I know how to find a Hall set thought, but that's a slightly different variation of the problem. – Wesley Strik Jan 15 at 19:55

## 1 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.)

• Thank you, this explained exactly what I did not understand, and this was precisely what I was doing when I got stuck, but I was missing the formal argument to make it a coherent whole- if that makes sense. – Wesley Strik Jan 15 at 22:07