Function Repository Resource:


Source Notebook

The Gallai–Edmonds decomposition of a graph

Contributed by: Daniel McDonald


gives the Gallai–Edmonds decomposition of the graph g.


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


Basic Examples (3) 

Define a graph g:

g = Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6, 5 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 8, 8 \[UndirectedEdge] 9, 7 \[UndirectedEdge] 9}, VertexLabels -> "Name"]

Find the Gallai-Edmonds decomposition of g:

ged = ResourceFunction["GallaiEdmondsDecomposition"][g]

Visualize it, with a maximum matching highlighted:

 HighlightGraph[g, FindIndependentEdgeSet[g], GraphHighlightStyle -> "Thick"], Thread[Labeled[ged, {"D(g)", "A(g)", "C(g)"}]]]


Daniel McDonald

Version History

  • 1.0.0 – 21 June 2021

License Information