Maximal Matching

Definition

Maximal Matching

A matching is called maximal if there is no matching with .

Example: The highlighted edge sets below show a matching , a maximal matching , and a maximum matching .

Examples

Maximal but not maximum

Consider the path graph with vertices and edges , , and .

The matching is maximal, because no additional edge can be added without sharing an endpoint with .

However, it is not maximum, because the matching has larger size.