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.


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\}$.


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.