structural:summarization
Constructive proof without flow concepts

No vertex in a vertex cover can cover more than one edge of M {\displaystyle M} (because the edge half-overlap would prevent M {\displaystyle M} from being a matching in the first place), so if a vertex cover with | M | {\displaystyle |M|} vertices can be constructed, it must be a minimum cover.

To construct such a cover, let U {\displaystyle U} be the set of unmatched vertices in A {\displaystyle A} (possibly empty), and let Z {\displaystyle Z} be the set of vertices that are either in U {\displaystyle U} or are connected to U {\displaystyle U} by alternating paths (paths that alternate between edges that are in the matching and edges that are not in the matching). Let

Every edge e {\displaystyle e} in E {\displaystyle E} either belongs to an alternating path (and has a right endpoint in K {\displaystyle K}), or it has a left endpoint in K {\displaystyle K}. For, if e {\displaystyle e} 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 A ∖ Z {\displaystyle A\setminus Z}. Alternatively, if e {\displaystyle e} 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 e {\displaystyle e} to it. Thus, K {\displaystyle K} forms a vertex cover.

Additionally, every vertex in K {\displaystyle K} is an endpoint of a matched edge.For, every vertex in A ∖ Z {\displaystyle A\setminus Z} is matched because Z {\displaystyle Z} is a superset of U {\displaystyle U}, the set of unmatched left vertices.And every vertex in B ∩ Z {\displaystyle B\cap Z} must also be matched, for if there existed an alternating path to an unmatched vertex then changing the matching by removing the matched edges from this path and adding the unmatched edges in their place would increase the size of the matching. However, no matched edge can have both of its endpoints in K {\displaystyle K}. Thus, K {\displaystyle K} is a vertex cover of cardinality equal to M {\displaystyle M}, and must be a minimum vertex cover.