Find the minimum vertex cover for a Bipartite Graph, if we are given the maximum Bipartite Matching

Question

From Konig's Theorem, the size of Maximum Matching (|M|) and minimum vertex cover is the same. Now we can include both ends of the matching in the vertex cover to find a vertex cover, but its size will be 2|M|. So I considered choosing a matching edge and then checking the degree of both ends. And then include the vertex with the higher degree. Suppose the degree of both ends is the same. We can include either. I tried this with a few examples I could think of it worked. But I am not sure of the algorithm. Is this correct? Also, if not, can anyone provide any counter example.?

Answer 1

Here is a counterexample:

Here, the maximum matching we have chosen is $M = \{bx, cy, dz\}$. If we pick the highest-degree endpoint of each edge in $M$, we will pick $b$ from $bx$, $y$ from $cy$, and $z$ from $dz$.

This is not a vertex cover. To get a vertex cover, we must pick $x$ from $bx$, because that is the only choice which can cover the edge $ax$.