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, thenthere 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.
@article{10_37236_2514,
author = {Vadim E. Levit and Eugen Mandrescu},
title = {A set and collection lemma},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/2514},
zbl = {1300.05230},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2514/}
}
TY - JOUR
AU - Vadim E. Levit
AU - Eugen Mandrescu
TI - A set and collection lemma
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/2514/
DO - 10.37236/2514
ID - 10_37236_2514
ER -
%0 Journal Article
%A Vadim E. Levit
%A Eugen Mandrescu
%T A set and collection lemma
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2514/
%R 10.37236/2514
%F 10_37236_2514
Vadim E. Levit; Eugen Mandrescu. A set and collection lemma. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/2514
