匹配生成多項式

圖 中的一個 -匹配 是一個包含 條邊的集合，其中任意兩條邊都沒有公共頂點（即，大小為 的一個 獨立邊集）。令 為圖 的 -匹配 的數量，其中 （因為由零條邊組成的空集 始終是一個 0-匹配）並且 是圖 的 邊數。那麼，匹配生成多項式直接編碼了圖 的 -獨立邊集 的數量，並由下式定義

(1)

其中 是圖 的 匹配數。

匹配生成多項式對於圖的不相交併是可乘的，因此對於圖 和 ,

(2)

其中 表示圖的並。

匹配生成多項式 與 匹配多項式 的關係為

(3)

（Ellis-Monaghan 和 Merino 2008）以及

(4)

匹配生成多項式與獨立多項式密切相關。特別地，由於線圖 中的獨立邊集對應於原始圖 中的獨立頂點集，因此圖 的匹配生成多項式等於 線圖 的獨立多項式（Levit 和 Mandrescu 2005）。

圖 具有完美匹配 當且僅當

(5)

其中 是圖 的頂點數。

許多命名圖的預計算匹配生成多項式將可以使用變數 透過以下方式獲得GraphData[graph,"MatchingGeneratingPolynomial"][x]。

下表總結了一些常見圖類的匹配生成多項式的閉合形式。這裡， 是第二類合流超幾何函式， 是拉蓋爾多項式，而 是盧卡斯多項式。

圖
完全圖
完全二分圖
圈圖
空圖
星圖