A set and collection lemma (Q405128): Difference between revisions

Summary: A set \(S\subseteq V(G)\) is independent if no two vertices from \(S\)~are adjacent. Let \(\alpha\left( G\right) \) stand for the cardinality of a largest independent set.{ }In this paper we prove that if \(\Lambda\) is a nonempty collection of maximum independent sets of a graph \(G\), and \(S\) is an independent set, then there is a matching from \(S-\bigcap\Lambda\) into \(\bigcup\Lambda-S\), and \(\left| S\right| +\alpha(G)\leq\left| \bigcap\Lambda\cap S\right| +\left| \bigcup\Lambda\cup S\right| \). Based on these findings we provide alternative proofs for a number of~well-known lemmata, such as the maximum stable set lemma due to \textit{C. Berge} [Graphs. Amsterdam-New York-Oxford: North-Holland (1985; Zbl 0566.05001)] and the clique collection lemma due to \textit{A. Hajnal} [Can. J. Math. 17, 720--724 (1965; Zbl 0129.39901)].