
doi: 10.1007/bf02579151
\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=\{b\in V;\quad [a,b]\in V\},\quad F[A]=\cup_{a\in A}F.\) 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\). 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.
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), perfect matching, compressed set, Other combinatorial set theory
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.), perfect matching, compressed set, Other combinatorial set theory
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 5 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
