The lower matching number of a graph is the minimum size of a maximal independent edge set. The (upper) matching number may be similarly defined as the largest size of an independent edge set. The lower matching number of a disconnected graph is the sum of the lower matching numbers of its connected components. The lower matching number of common graph classes sometimes appears to follow an "obvious" pattern but actually differs for certain values. Examples of this sort occur for the n×n grid and torus grid graphs, where values for smallish n agree with ⌈n^2/3⌉ but for larger n may be one larger.

independent edge set | matching number | well-covered graph