The Gallai–Edmonds decomposition of a graph g is the partition {D(g),A(g),C(g)} of its vertices, where D(g) consists of every vertex v for which there exists a maximum matching of g that misses v, A(g) consists of every vertex v that is not in D(g) but neighbors some vertex in D(g) and C(g) consists of all remaining vertices.

Given the Gallai–Edmonds decomposition {D(g),A(g),C(g)} of a graph g, the set A(g) is a Tutte–Berge witness set for g (i.e. setting U=A(g) minimizes over all subsets U of the vertex set V of g the quantity (|V|+|U|-o(g-U))/2, where o(g-U) counts the odd components of g-U; by the Tutte–Berge formula, this minimized quantity equals the size of a maximum matching of g), C(g) is the union of the even components of g-A(g), D(g) is the union of the odd components of g-A(g) and each odd component of g-A(g) is factor-critical (a graph is factor-critical if it has no perfect matching, but any subgraph obtained by deleting a single vertex does have a perfect matching).