# Minimum Vertex cover in a bipartite graph [closed]

Show that the problem of finding the minimum vertex cover in a bipartite graph reduces to finding a maximum flow. Describe the reduction in a precise and concise way.

-

Why linear programming as a tag? – The Unfun Cat Nov 9 '12 at 10:28
@david: You are posting here for the first time. So let me point out some general rules to get a useful answer. Say what you have tried, where have you been stuck? Also it might be helpful not to phrase your question as a textbook question. – A.Schulz Nov 9 '12 at 10:40
– The Unfun Cat Nov 9 '12 at 10:52
– JeffE Nov 9 '12 at 16:15

## closed as not a real question by A.Schulz, JeffE, Gilles♦Nov 9 '12 at 22:05

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, see the FAQ.

## 1 Answer

Call the two partitions of the nodes $A$ and $B$. Add two new nodes, a source $s$ and a sink $t$. Connect the start node to all nodes in $A$ with an edge with max capacity of one. Connect all the nodes in $B$ to the sink with edges with a max capacity of one. And lastly give all the original edges in the graph a max capacity of one. Now finding the max flow from $s$ to $t$ will find the minimum vertex cover.

For each edge $(u,v)$ included in the max-flow, the nodes $u$ and $v$ will be a part of the minimum vertex cover.

Draw this and you will understand.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 11, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9363282322883606, "perplexity_flag": "head"}