Matching (graph theory)

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching.

Finding a largest matching in a bipartite graph can be treated as a network flow problem. Finding a largest matching in a general graph is much more difficult; it can be done using Edmonds' blossom algorithm.

Definitions

Given a graph G = (V, E), a matching M in G is a set of pairwise non-adjacent edges, none of which are loops; that is, no two edges share common vertices.

M

{\displaystyle M}

is a matching of

U

⊆

V

{\displaystyle U\subseteq V}

if every vertex in

U

{\displaystyle U}

is incident with an edge in

M

{\displaystyle M}

.

A vertex is matched (or saturated) if it is an endpoint of one of the edges in the matching. Otherwise the vertex is unmatched (or unsaturated).

A maximal matching is a matching M of a graph G that is not a subset of any other matching. A matching M of a graph G is maximal if every edge in G has a non-empty intersection with at least one edge in M. The following figure shows examples of maximal matchings (red) in three graphs.