I have been trying to understand the proof of the König's following theorem on bipartite graphs: "The maximum cardinality of a matching in a graph $G$ is equal to the minimum cardinality of a vertex cover.". While working on it, I have found a simpler interpretation of the proof than the one given in Graph Theory book by Reinhard Diestel. Is the proof correct, or am I missing something here?
We can form the minimum vertex cover candidate by selecting the elements of the matchings that are connected to an unmatched element if there is one in the matching, and by selecting the element from the left hand side (or the right hand side, but consistently) otherwise. The selection made in the example graph can be shown to be the minimum vertex since:
- All the edges in the matching are covered by it since we have constructed this using one element of every matching,
- All the edges that are connected to the unmatched elements are covered since we have selected the minimum vertex cover according to that. The critical point to emphasize here is that only a single element of a pair can be connected to a one (or many) unmatched element(s), because otherwise we would have an augmenting path that could have been used to form an additional matching which would violate the idea of the maximum matching.
For the K3-3 graph, the algorithm randomly picks a side to select the vertices from the maximum matching to form the minimum vertex cover. This is due to the fact that all elements from both sides are matched. I believe the size of the maximum matching is 3 for K3-3, and it can be seen that minimum vertex cover is of size 3 too.