TOPICS

# Matching Number

The (upper) matching number of 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

 (1)

where is the number of -matchings 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

 (2)

where is the vertex count of , is the floor function. Equality occurs only for a perfect matching, and graph has a perfect matching iff

 (3)

where is the vertex count of .

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

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

If a graph has no isolated points, then

 (4)

where is the matching number, 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"].

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

## Explore with Wolfram|Alpha

More things to try:

## References

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

## Cite this as:

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