A Set and Collection Lemma

Abstract

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\vert S\right\vert +\alpha(G)\leq\left\vert \bigcap\Lambda\cap S\right\vert +\left\vert \bigcup\Lambda\cup S\right\vert $.

Based on these findings we provide alternative proofs for a number of well-known lemmata, such as the "Maximum Stable Set Lemma" due to Claude Berge and the "Clique Collection Lemma" due to András Hajnal.