= Matching
{disambiguate=graph theory}
{wiki}
= Matching
{synonym}
= Matching in a graph
{synonym}
= Matchings in a graph
{synonym}
= Graph matching
{synonym}
A <matching in a graph> is a <set> $M$ of <edges> of an <undirected graph> with no shared endpoints: each <vertex> has capacity for at most one selected <edge>. It describes simultaneous compatible pairs, such as jobs assigned to distinct available workers, or tasks each occupying two resources that cannot be shared. The empty <set> is a valid <matching in a graph>.<Graph Theory by Reinhard Diestel>[Matching, Covering and Packing, opening paragraph, printed p. 1: independent edges and matchings]{ref}
For a finite <simple graph> $G=(V,E)$, write $x_e=1$ when $e$ is selected and $x_e=0$ otherwise. The vertex capacity constraint is exactly
$$
x_e\in\{0,1\}\quad(e\in E),\qquad
\sum_{e\in E:\,v\in e}x_e\leq1\quad(v\in V).
$$
These are constraints on a discrete selection, not a requirement that every <vertex> be used. A <matching in a graph> with <matching saturation> of all <vertices> is a <perfect matching>; an <unmatched vertex in a matching> uses none of its capacity.
The objective must be specified separately. A <maximum cardinality matching> selects as many <edges> as possible; a <maximum-weight matching> selects the greatest total benefit; a <minimum-weight perfect matching> minimizes cost while requiring every <vertex> to be paired. A <maximal matching> only says that no additional <edge> fits alongside the current choices. The four-<vertex> <path graph> below separates these notions: choosing the middle <edge> blocks both outer <edges>, yet replacing it by those two <edges> pairs more <vertices>.
This model is useful because conflicts are local at <vertices>, while the quality of a selection can depend on coordinated changes along a whole <augmenting path in a matching>. A <greedy matching> gives a quick feasible selection; <Berge's theorem> explains when searching for such changes has reached a <maximum cardinality matching>. Repeating the pairing problem over time leads instead to <proper edge colouring>, where each time slot is a <matching in a graph>.
Back to article page
