匹配，也称为独立边集，在图 
上，是 
的一组边，使得没有两个边共享一个公共顶点。
在具有 
个节点的图上，匹配的边数不可能超过 
。当存在具有 
条边的匹配时，它被称为完美匹配。当存在一个匹配，留下单个顶点未匹配时，它被称为近完美匹配。
虽然并非所有图都具有完美匹配，但每个图都存在一个最大的匹配（通常称为最大匹配或最大独立边集）。这个最大匹配的大小称为 
的匹配数，并表示为 
。
图中匹配的数量有时被称为 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.