Coupon Accepted Successfully!


Maximal Maching

It is a matching to which no edge in the graph can be added.

e.g. in a complete graph of three vertices (i.e. a triangle) any single edge is a maximal matching. The edges shown by heavy lines.


Clearly, a graph may have many different maximal matchings and of different sizes. Among these, the maximal matchings with the largest number of edges are called largest maximal matchings.

In Fig. (b), a largest maximal matching is shown in heavy lines. The number of edges in a largest maximal matching called
 matching number of the graph.

Test Your Skills Now!
Take a Quiz now
Reviewer Name