On an obstruction for perfect matchings (Q793753)

\textit{K. Steffens} [Can. J. Math. 29, 165-168 (1976; Zbl 0324.05122)] proved a necessary and sufficient condition for the existence of perfect matchings in countable graphs. He presented a substructure (called ''compressed set'') which obstructs perfect matchings in any graph, and proved that in the countable case this is the only possible obstruction for perfect matchings. In the paper under review, some properties of compressed sets are studied. Let \(G=(V,E)\) be an undirected graph. If \(S\subseteq V\) then G[S] denotes the graph (S,\(E\cap\left( \begin{matrix} S\\ 2\end{matrix} \right))\) and \(G-S\) denotes G[V-S]. Let \(F\subseteq E\), \(A\subseteq V\) and \(a\in V\). Then set \(F<a>=\{b\in V;\quad [a,b]\in V\},\quad F[A]=\cup_{a\in A}F<a>.\) If G contains a compressed set then it is said to be obstructed. The main results are the following ones. Theorem 1: If G is unobstructed and \(a\in V\) then G-\(\{\) a,\(x\}\) is unobstructed for some \(x\in E<a>\). Theorem 2: If G is unobstructed and G- F[V] is countable for some matching F then G possesses a perfect matching. Theorem 3: If G is obstructed and \(F\subseteq E\) then \(L=(V,F)\) is obstructed. Theorem 4: If \(S\subseteq V\) and both G[S] and G-S are unobstructed then G is unobstructed.