Matching

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.

graph
complete graph
complete bipartite graph
cycle graph
empty graph
path graph

REFERENCES

Hopcroft, J. and Karp, R. "An  Algorithm for Maximum Matching in Bipartite Graphs." SIAM J. Comput. 2, 225-231, 1975.

Lovász, L. and Plummer, M. D. Matching Theory. Amsterdam, Netherlands: North-Holland, 1986.

Pemmaraju, S. and Skiena, S. "Matching." §8.4 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 343-351, 2003.

Skiena, S. "Matching." §6.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 240-246, 1990.

Zwick, U. "Lecture Notes on: Maximum Matching in Bipartite and Non-Bipartite Graphs." 2009. http://www.cs.tau.ac.il/~zwick/grad-algo-0910/match.pdf.