We have the following bi-adjacency matrix of a bipartite graph:
\begin{bmatrix}0&0&1&0&1&0\\1&1&0&1&0&1\\0&0&1&0&1&0\\1&1&1&1&0&1\\0&0&1&0&1&0\\1&1&0&1&1&1\end{bmatrix}
My problem is as follows: Koning's lemma states that the cardinality of the maximum matching is equal to the cardinality of the minimum vertex cover. In this bi-adjacency matrix, I can find 5 matchings (=cardinality of the maximum matching). There are namely three rows, 1, 3 and 5 with the same entries. So there has to be 2 that can match and 1 that can't, leaving with 5 matchings.
I can't find any way, however, to find a minimum vertex cover equal to 5. All the sets of minimum vertex covers I've found have a cardinality of 6.
Can someone point out what the issue here is? Is the maximum matching equal to 6 instead of 5?
Best Answer
Whenever you have an obstacle like that to finding matchings, it should help us find a vertex cover.
In this instance, because rows $1,3,5$ can only be matched to columns $3$ and $5$, adding columns $3$ and $5$ to our vertex cover takes care of all the entries in those rows, as well. So there is a vertex cover of size $5$: take rows $2,4,6$ and columns $3,5$.