完美匹配

图的完美匹配是一个 匹配 （即，独立边集），其中图的每个顶点恰好与匹配的一条边相关联。 因此，完美匹配是包含 条边的 匹配 （最大可能），这意味着完美匹配仅在具有偶数个顶点的图上才有可能。 完美匹配有时被称为完全匹配或 1-因子。

上面展示了立方体图的九个完美匹配。

请注意，容易混淆的是，被称为完美图的图类与具有完美匹配的图类是不同的。

预计算的具有完美匹配的图返回真对于GraphData[g,"PerfectMatching"] 在 Wolfram 语言中。

虽然不是所有图都具有完美匹配，但所有图都具有最大独立边集（即，最大匹配；Skiena 1990, p. 240; Pemmaraju 和 Skiena 2003, pp. 29 和 343）。 此外，每个完美匹配都是一个最大独立边集。 一个图要么具有与最大匹配相同数量的完美匹配（对于完美匹配图），要么没有完美匹配（对于没有完美匹配图）。

图 具有完美匹配 当且仅当 其匹配数 满足

其中 是 的顶点数。

在 , 4, 6, ... 个顶点上具有完美匹配的简单图的数量分别是 1, 6, 101, 10413, ..., (OEIS A218462)，而相应的连通简单图的数量分别是 1, 5, 95, 10297, ... (OEIS A218463)。

上面展示的图是一个没有完美匹配的 16 节点图，它在 Wolfram 语言中实现为GraphData["NoPerfectMatchingGraph"].

每个具有偶数个顶点的连通顶点传递图都有一个完美匹配，并且具有奇数个顶点的连通顶点传递图中的每个顶点都会被一个覆盖所有剩余顶点的匹配所遗漏（Godsil 和 Royle 2001, p. 43；即，它具有近完美匹配）。

每个具有偶数个顶点的无爪连通图都有一个完美匹配 (Sumner 1974, Las Vergnas 1975)。

彼得森定理指出，每个没有桥的立方图都有一个完美匹配（Petersen 1891；Skiena 1990, p. 244）。 事实上，这个定理可以扩展为：“每个具有 0、1 或 2 个桥的立方图都有一个完美匹配。”

部分由 Tutte 定理得出的结果表明，图 （其中 是顶点集， 是边集）没有完美匹配 当且仅当 存在一个集合 ，其移除导致奇数大小的分量比 （ 的基数；Tutte 1947；Pemmaraju 和 Skiena 2003, p. 344）更多。