A matching, also called an independent edge set, on a graph 
is a set of edges of 
such that no two sets share a vertex in common.
It is not possible for a matching on a graph with 
nodes to exceed 
edges. When a matching with 
edges exists, it is called a perfect
matching. When a matching exists that leaves a single vertex unmatched, it is
called a near-perfect matching.
While not all graphs have perfect matchings, a largest matching (commonly known as a maximum matching or maximum independent
edge set) exists for every graph. The size of this maximum matching is called
the matching number of 
and is denoted 
.
The number of matchings in a graph is sometimes called the Hosoya index.
A maximal independent edge set, which is different from a maximum independent edge set, is a matching that cannot be enlarged by simply adding an edge. Such matchings are easy to compute, but are not necessarily maximum independent edge sets. A maximal independent edge set on a general graph can be found using MaximalMatching[g] in the Wolfram Language package Combinatorica` , but not using a using built-in function in the Wolfram Language.
The blossom algorithm can be used to find a maximum independent edge set in a general graph, while the simpler Hungarian maximum matching algorithm can be used for bipartite graphs. A maximum independent edge set can be computed in the Wolfram Language using FindIndependentEdgeSet[g].
Let the number of distinct 
-matchings
of a graph with 
vertices be denoted 
.
Then 
(since the empty
set consisting of no edges is always a 0-matching) and 
, where 
is the edge count of 
.
The matching polynomial is defined by
 |
and the matching-generating polynomial by
 |
The numbers of distinct 
-matchings
for various specials classes of graphs are summarized in the following table, where
denotes a factorial,
is a double
factorial, 
is a binomial coefficient, and 
is the discrete delta function.
Algorithm for Maximum Matching in Bipartite Graphs."
SIAM J. Comput. 2, 225-231, 1975.Lovász, L. and
Plummer, M. D.