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