Function Repository Resource:

# GallaiEdmondsDecomposition

The Gallai–Edmonds decomposition of a graph

Contributed by: Daniel McDonald
 ResourceFunction["GallaiEdmondsDecomposition"][g] gives the Gallai–Edmonds decomposition of the graph g.

## Details

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).

## Examples

### Basic Examples (3)

Define a graph g:

 In[1]:=
 Out[1]=

Find the Gallai-Edmonds decomposition of g:

 In[2]:=
 Out[2]=

Visualize it, with a maximum matching highlighted:

 In[3]:=
 Out[3]=

Daniel McDonald

## Version History

• 1.0.0 – 21 June 2021