TOPICS
Search

Matching Number


The (upper) matching number nu(G) of graph G, 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

 M(x)=sum_(k=0)^(nu(G))Phi_kx^k
(1)

where Phi_k is the number of k-matchings of a graph G. The notations c(G), rho_s(G), or alpha^'(G) 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.

nu(G) satisfies

 nu(G)<=|_1/2n_|,
(2)

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

 |G|=2nu(G),
(3)

where |G|=n is the vertex count of G.

The matching number nu(G) of a graph G is equal to the independence number alpha(L(G)) of its line graph L(G).

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 G has no isolated points, then

 alpha^'(G)+beta^'(G)=|G|,
(4)

where alpha^'(G) is the matching number, beta^'(G) is the size of a minimum edge cover, and n=|G| is the vertex count of G (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.

Cite this as:

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

Subject classifications