# A Set and Collection Lemma

Keywords:
Matching, Independent set, Stable set, Core, Corona, Clique

### 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.