= Maximum cardinality matching
{wiki}
= Maximum matching
{synonym}
A <maximum cardinality matching> is a <matching in a graph> with as many <edges> as any <matching in a graph> of the same <graph>. It has <cardinality> $\nu(G)$, the <matching number>, and need not be unique or be a <perfect matching>. For example, any single <edge> of a <triangle in a graph> is a <maximum cardinality matching>, but leaves one <vertex> unmatched. <Berge's theorem> characterizes these optima by the absence of an <augmenting path in a matching>.
Back to article page
