Let M be a matching in graph G, and let S be the set of vertices matched by M.

Prove that there exists amaximummatching in G under which all vertices in S are matched?

Printable View

- May 5th 2012, 10:03 PMafrochumGraph Theory proof
Let M be a matching in graph G, and let S be the set of vertices matched by M.

Prove that there exists a__maximum__matching in G under which all vertices in S are matched?