# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

The Gallai–Edmonds decomposition of a graph

Contributed by:
Daniel McDonald

ResourceFunction["GallaiEdmondsDecomposition"][ gives the Gallai–Edmonds decomposition of the graph |

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

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]= |

- 1.0.0 – 21 June 2021

This work is licensed under a Creative Commons Attribution 4.0 International License