# How to find a minumum vertex cover from a maximum matching in a bipartite graph?

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.

https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)

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