# How do you find all minimal vertex cover of bipartite graph $G$?

Let $$G$$ be a bipartite graph with vertex set $$V=V_1 \cup V_2$$. If $$\mid V_1\mid= n$$ and $$\mid V_2\mid=m$$ with $$m\leq n$$, then how to find all minimal vertex cover?

• Minimal vertex covers can be computed easily from maximal matchings (for bipartite graphs). This paper gives a method to enumerate all maximal matchings. – Mike Earnest May 16 at 16:41
• Thank you so much for the paper. – Martia May 18 at 2:19

This is largely dependent from bipartite graph to bipartite graph, Konig's Theorem states that the size of the minimal vertex cover is the size of the maximal matching. In your case, the largest matching can be at most $$m$$. Also see Hall's Theorem.