[Math] How to find a minumum vertex cover from a maximum matching in a bipartite graph

algorithmsgraph theory

Konig's theorem states that for a bipartite graph the number of vertices in the minimum vertex cover equals the number of edges in a maximum matching.


For example given a bipartite graph with vertices 1,2,…,10 (with 5 on the left and 5 the right) and edges 1-6, 1-8, 2-8, 3-7, 3-8, 3-9, 4-8, 5-7, 5-8, 5-10. A maximal matching is 1-6, 2-8, 3-7, 5-10.

But how do you find a minimum vertex cover given a set of edges for a maximum matching? Such as 1, 8, 3, 5 in the example above.

Best Answer

The proof in the article you linked gives such an explicit construction. In your example, if $L = \{1,2,3,4,5\}$ , $R = \{6,7,8,9,10\}$ are the partite sets, let $Z$ be the set of vertices that are either unmatched vertices of $L$ or connected to an unmatched vertex in $L$ by an alternating path. $4$ is the only unmatched vertex in $L$ and the only vertices we can reach by alternating paths are $2$ and $8$, so $Z = \{2,4,8\}$. A minimum vertex cover is then given by $(L\setminus Z) \cup (R\cap Z) = \{1,3,5,8\}$.