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

REFERENCES

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