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.
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.