source to every vertex and from every vertex to the sink , and of capacity from to for any . The size of the maximum matching in is the size of a maximum flow in , which, in turn, is the size of a minimum cut in the network , as follows from the max-flow min-cut theorem. Let be a minimum cut. Let and , such that and . Then the minimum cut is composed only of edges going from to or from to , as any edge from to would make the size of the cut infinite. Therefore, the size of the minimum cut is equal to . On the other hand, is a vertex cover, as any edge that is not incident to vertices from and must be incident to a pair of vertices from and , which would contradict the fact that there are no edges between and . Thus, is a minimum vertex cover of . Constructive proof without flow concepts No vertex in a vertex cover can cover more than one edge of (because the edge half-overlap would prevent from being a matching in the first place), so if a vertex cover with vertices can be constructed, it must be a minimum cover. To construct such a cover, let be the set of unmatched vertices in (possibly empty), and let be the set of vertices that are either in or are connected to by alternating paths (paths that alternate between edges that are in the matching and edges that are not in the matching). Let Every edge in either belongs to an alternating path (and has a right endpoint in ), or it has a left endpoint in . For, if is matched but not in an alternating path, then its left endpoint cannot be in an alternating path (because two matched edges can not share a vertex) and thus belongs to . Alternatively, if is unmatched but not in an alternating path, then its left endpoint cannot be in an alternating path, for such a path could be extended by adding to it. Thus, forms a vertex cover. Additionally, every vertex in is an endpoint of a matched edge. For, every vertex in is matched because is a superset of , the set of unmatched left vertices. And every vertex in must also be matched, for if there existed an alternating path to an