Maximal tight sets and the Edmonds-Gallai decomposition for matchings (Q1086254)

A set A of vertices of a graph G is matchable if some matching of G saturates all vertices of G, and hypomatchable if all subsets \(A\setminus a\) (a\(\in A)\) are matchable. The Edmonds-Gallai decomposition theorem for matchings in finite graphs asserts the following: Let G be a graph and A the set of those vertices of G which are missed by at least one maximal matchable set in G; let B be the set of all other vertices which are adjacent to A, and C the set of remaining vertices. Then (1) each component of G induced on A is hypomatchable, (2) for any matching M of G which saturates the vertices of some maximal matchable set (a) each \(x\in B\) is matched with a vertex of A, (b) each component induced by A has all but one vertex internally matched by M, and (c) all vertices of C are internally matched by M. The author generalizes this result to a statement about infinite graphs. A tight set A is a matchable set for which every matching saturating the vertices of A has all edges intersecting A internal to A. The closure of a tight set A consists of A together with those vertices all of whose neighbours belong to A. The union of the closures of all tight sets in G is called the kernel of G. The generalization of the Edmonds-Gallai theorem proved here gives a decomposition of the kernel of an arbitrary graph G into sets A, B, and C, with properties similar to those above, except that maximal matchable sets are replaced by maximal tight sets. It turns out that if G has a maximal matchable set (and some infinite graphs don't), then G is its own kernel, and the maximal tight sets are precisely the maximal matchable sets. Therefore the classical Edmonds- Gallai theorem applies to all graphs which have a maximal matchable set. These include, in addition to finite graphs, all locally finite graphs, all countable graphs, and all graphs without infinite paths (this last fact being a result of R. Schmidt). That the Edmonds-Gallai decomposition theorem holds for locally finite graphs has been previously noted by \textit{F. Bry} and \textit{M. LasVergnas} [Combinatorica 2, 229-235 (1982; Zbl 0518.05051)]. The proofs in the present paper use some earlier work of the author as well as that of R. Aharoni.