Download Wolfram Notebook

The (upper) matching number of a graph , sometimes known as the edge independence number, is the size of a maximum independent edge set. Equivalently, it is the degree of the matching-generating polynomial

where is the number of matchings of size of a graph . The notations , , or are sometimes also used.

The matching number is also the size of a largest maximal independent edge set, while the size of a smallest maximal independent edge set is called the lower matching number.

satisfies

where is the vertex count of and is the floor function. A graph has a perfect matching iff

where is the vertex count of .

If a graph on vertices is traceable, then every other edge of a Hamiltonian path gives a matching of size . Thus traceability implies .

The matching number of a graph is equal to the independence number of its line graph .

The König-Egerváry theorem states that the matching number equals the vertex cover number (i.e., size of a minimum vertex cover) for a bipartite graph.

If a graph has no isolated vertices, then

where is the size of a minimum edge cover and is the vertex count of (West 2000).

Precomputed matching numbers for many named graphs are available in the Wolfram Language using GraphData[graph, "MatchingNumber"].

See also

Lower Matching Number, Matching, Matching-Generating Polynomial, Matching Polynomial, Maximal Independent Edge Set, Maximum Independent Edge Set, Minimum Edge Cover

Explore with Wolfram|Alpha

References

West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

Referenced on Wolfram|Alpha

Matching Number

Cite this as:

Weisstein, Eric W. "Matching Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/MatchingNumber.html

Subject classifications