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:

  1. All the edges in the matching are covered by it since we have constructed this using one element of every matching,
  2. 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.

  • $\begingroup$ There's something I'm not quite clear about in your proof. Would you mind working out another example? Could you take a maximum matching in $K_{3,3}$ and show how your procedure leads to a minimum vertex cover? $\endgroup$
    – bof
    Dec 4 '20 at 15:34
  • $\begingroup$ @bof I have shown the K3,3 case, for which I needed to clarify the text a bit. I have my doubts regarding this proof too, so I would really appreciate if you could show me where I am wrong. Thank you for the ideas! $\endgroup$ Dec 5 '20 at 9:03
  • $\begingroup$ @AmitRajaraman Yes, that was a mistake, I have fixed it. Thanks for pointing it out... $\endgroup$ Dec 5 '20 at 9:04

Consider the example below given by Diestel. Your algorithm would conceivably choose the top right vertex and then the left vertices of the rest of the matching edges. But this is not a vertex cover: there is an edge going between the left and right vertices of the first and second matching edges, respectively, that is not covered.

Of course, in this case if we had been more lucky and chose all of the vertices from the right side, we would have gotten a vertex cover. But it is not difficult (and maybe instructive) to extend this to an example where neither choice gives you a vertex cover. (Hint: you only have to add one unmatched vertex of degree one to this example.)

Example from Diestel's graph theory

  • $\begingroup$ Thank you, I believe it would need a few more steps to work for any condition, but it would make the proof and the covering method harder than the original one that depends on the alternating paths. $\endgroup$ Dec 5 '20 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.