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