Matchings and related terminology

A matching MM of an undirected graph GG is any collection of its edges that have no end-vertex in common. In other words, each edge in MM uniquely pairs or matches two vertices. We refer to the number of edges in a matching MM as the size of the matching MM.

If a vertex appears as an end-vertex of an edge in MM, we say it is matched by MM. Otherwise, we say it is unmatched by MM. Some examples of matchings in graphs are shown in the set of slides below.

Get hands-on with 1200+ tech skills courses.