匹配，也稱為獨立邊集，在圖 
上，是 
的一組邊，使得沒有兩個邊共享一個公共頂點。
在具有 
個節點的圖上，匹配的邊數不可能超過 
。當存在具有 
條邊的匹配時，它被稱為完美匹配。當存在一個匹配，留下單個頂點未匹配時，它被稱為近完美匹配。
雖然並非所有圖都具有完美匹配，但每個圖都存在一個最大的匹配（通常稱為最大匹配或最大獨立邊集）。這個最大匹配的大小稱為 
的匹配數，並表示為 
。
圖中匹配的數量有時被稱為 Hosoya 指數。
最大獨立邊集，它與最大獨立邊集不同，是一個無法透過簡單新增邊來擴大的匹配。這種匹配很容易計算，但不一定是最大獨立邊集。可以使用以下方法在一般圖上找到最大獨立邊集：MaximalMatching[g] 在 Wolfram 語言 包中Combinatorica`，但不是使用 Wolfram 語言中的內建函式。
花演算法可用於在一般圖中找到最大獨立邊集，而更簡單的匈牙利最大匹配演算法可用於二分圖。可以使用以下方法在 Wolfram 語言中計算最大獨立邊集：FindIndependentEdgeSet[g]。
令具有 
個頂點的圖的不同 
-匹配的數量表示為 
。那麼 
（因為由沒有邊組成的空集始終是 0-匹配）並且 
，其中 
是 
的邊數。
匹配多項式定義為
 |
和匹配生成多項式定義為
 |
-匹配的數量，其中 
表示
是
是
是離散 delta 函式。
Algorithm for Maximum Matching in Bipartite Graphs." SIAM J. Comput. 2, 225-231, 1975.Lovász, L. and Plummer, M. D.