Loading....
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.
 

538.png 


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