完美匹配

圖的完美匹配是一個 匹配 （即，獨立邊集），其中圖的每個頂點恰好與匹配的一條邊相關聯。 因此，完美匹配是包含 條邊的 匹配 （最大可能），這意味著完美匹配僅在具有偶數個頂點的圖上才有可能。 完美匹配有時被稱為完全匹配或 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）更多。