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.