Gallai-Edmonds theorem

Gallai-Edmonds theorem is a fundamental result in graph theory that helps understand the structure of maximum matchings—pairings of nodes such that no node is used more than once—in a graph. It categorizes vertices into three groups: those always matched in every maximum matching, those never matched, and those that can be matched depending on the situation. The theorem provides a precise way to break down a graph into these parts, revealing how the structure influences possible matchings. This understanding aids in solving optimization problems related to pairing or scheduling in various real-world systems.