% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1.40}{21(1)}{2014}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
%\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
%\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf A Set and Collection Lemma}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Vadim E. Levit\\
\small Department of Computer Science and Mathematics\\[-0.8ex]
\small Ariel University\\[-0.8ex]
\small Ariel 40700, Israel\\
\small\tt levitv@ariel.ac.il\\
\and
Eugen Mandrescu \\
\small Department of Computer Science\\[-0.8ex]
\small Holon Institute of Technology\\[-0.8ex]
\small Holon 58102, Israel\\
\small\tt eugen\_m@hit.ac.il
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Oct 25, 2011}{Feb 19, 2014}{Feb 28, 2014}\\
\small Mathematics Subject Classifications: 05C69, 05C70, 05A20}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  A set $S\subseteq V(G)$ is \textit{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

\begin{itemize}
\item there is a matching from $S-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda$ into $%
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-S$, and

\item $\left\vert S\right\vert +\alpha(G)\leq\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\cap S\right\vert +\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\cup S\right\vert $.

\end{itemize}

Based on these findings we provide alternative proofs for a number of
well-known lemmata, such as the \textquotedblleft\textit{Maximum Stable Set
Lemma}\textquotedblright\ due to Claude Berge and the \textquotedblleft%
\textit{Clique Collection Lemma}\textquotedblright\ due to Andr\'{a}s Hajnal.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} matching; independent set; stable set; core; corona; clique
\end{abstract}

\section{Introduction}
Throughout this paper $G=(V,E)$ is a simple (i.e., a finite, undirected,
loopless and without multiple edges) graph with vertex set $V=V(G)$ and edge
set $E=E(G)$. If $X\subseteq V$, then $G[X]$ is the subgraph of $G$ spanned by
$X$. By $G-W$ we mean the subgraph $G[V-W]$, if $W\subseteq V(G)$, and we use
$G-w$, whenever $W$ $=\{w\}$.

The \textit{neighborhood} of a vertex $v\in V$ is the set $N(v)=\{w:w\in V$
\ \textit{and} $vw\in E\}$, while the \textit{neighborhood} of $A\subseteq V$
is $N(A)=N_{G}(A)=\{v\in V:N(v)\cap A\neq\emptyset\}$. By $\overline{G}$ we
denote the complement of $G$.

A set $S\subseteq V(G)$ is \textit{independent} (\textit{stable}) if no two
vertices from $S$ are adjacent, and by $\mathrm{Ind}(G)$ we mean the set of
all the independent sets of $G$. An independent set of maximum cardinality
will be referred to as a \textit{maximum independent set} of $G$, and the
\textit{independence number }of $G$ is $\alpha(G)=\max\{\left\vert
S\right\vert :S\in\mathrm{Ind}(G)\}$.

A matching (i.e., a set of non-incident edges of $G$) of maximum cardinality
$\mu(G)$ is a \textit{maximum matching}.

If $\alpha(G)+\mu(G)=\left\vert V\left(  G\right)  \right\vert $, then $G$ is
called a K\"{o}nig-Egerv\'{a}ry graph\textit{ }\cite{Dem1979, Ster1979}.

\begin{lemma}
[\textit{Maximum Stable Set Lemma}]\cite{Berge1981}, \cite{Berge1985} An
independent set $X$ is maximum if and only if every independent set $S$
disjoint from $X$ can be matched into $X$.
\end{lemma}

Let $\Omega(G)$ denote the family of all maximum independent sets of $G$ and
\begin{align*}
\mathrm{core}(G)  &  =%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\{S:S\in\Omega(G)\}\text{ \cite{LevMan2002a}, while }\\
\mathrm{corona}(G)  &  =%
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\{S:S\in\Omega(G)\}\text{ \cite{BorosGolLev2002}}.
\end{align*}


A set $A\subseteq V(G)$ is a \textit{clique} in $G$ if $A$ is independent in
$\overline{G}$, and $\omega\left(  G\right)  =\alpha\left(  \overline
{G}\right)  $.

Our main motivation has been the \textquotedblleft\textit{Clique Collection
Lemma}\textquotedblright\ due to Hajnal \cite{Hajnal1965}. Some recent
applications may be found in \cite{CEK2011,King2011, Rabern2011}.

\begin{lemma}
[\textit{Clique Collection Lemma}]\cite{Hajnal1965} If $\Gamma$ is a
collection of maximum cliques in $G$, then
\[
\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Gamma\right\vert \geq2\cdot\omega(G)-\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Gamma\right\vert .
\]

\end{lemma}

In this paper we introduce the \textquotedblleft\textit{Matching
Lemma}\textquotedblright. It is both a generalization and strengthening of a
number of observations including the \textquotedblleft\textit{Maximum Stable
Set Lemma}\textquotedblright\ due to Berge, and the \textquotedblleft%
\textit{Clique Collection Lemma}\textquotedblright due to Hajnal.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Results}

It is clear that the statement \textquotedblleft\textit{there exists a
matching from a set} $A$ \textit{into a set} $B$\textquotedblright\ is
stronger than just saying that $\left\vert A\right\vert \leq\left\vert
B\right\vert $. The \textquotedblleft\textit{Matching Lemma}\textquotedblright%
\ offers a tool validating existence of matchings and their corresponding inequalities.

\begin{lemma}
[Matching Lemma]\label{MatchLem}Let $S\in\mathrm{Ind}(G),X\in\Lambda
\subseteq\Omega(G)$, and $\left\vert \Lambda\right\vert \geq1$. Then the
following assertions are true:

\emph{(i)} there exists a matching from $S-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda$ into $%
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-S$;

\emph{(ii) }there exists a matching from $S\cap X-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda$ into $%
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-\left(  X\cup S\right)  $.
\end{lemma}

\begin{proof}
\emph{(i) }In order to prove that there is a matching from $S-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda$ into $%
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-S$, we use Hall's Theorem, i.e., we show that for every $A\subseteq S-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda$ we must have
\[
\left\vert A\right\vert \leq\left\vert N\left(  A\right)  \cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right)  \right\vert =\left\vert N\left(  A\right)  \cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-S\right)  \right\vert \text{.}%
\]

Assume, by way of contradiction, that Hall's condition is not satisfied. Let
us choose a minimal subset $\tilde{A}\subseteq S-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda$, for which $\left\vert \tilde{A}\right\vert >\left\vert N\left(
\tilde{A}\right)  \cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right)  \right\vert $.

There exists some $W\in\Lambda$ such that $\tilde{A}\nsubseteq W$, because
$\tilde{A}\subseteq S-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda$. Further, the inequality $\left\vert \tilde{A}\cap W\right\vert
<\left\vert \tilde{A}\right\vert $ and the inclusion%
\[
N(\tilde{A}\cap W)\cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right)  \subseteq N(\tilde{A})\cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right)  -W
\]
imply
\[
\left\vert \tilde{A}\cap W\right\vert \leq\left\vert N(\tilde{A}\cap
W)\cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right)  \right\vert \leq\left\vert N(\tilde{A})\cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right)  -W\right\vert ,
\]
because we have selected $\tilde{A}$ as a minimal subset satisfying
$\left\vert \tilde{A}\right\vert >\left\vert N\left(  \tilde{A}\right)
\cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right)  \right\vert $.

On the other hand,%
\[
\left\vert \tilde{A}\cap W\right\vert +\left\vert \tilde{A}-W\right\vert
=\left\vert \tilde{A}\right\vert >\left\vert N(\tilde{A})\cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right)  \right\vert =\left\vert N(\tilde{A})\cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right)  -W\right\vert +\left\vert N(\tilde{A})\cap W\right\vert .
\]
Consequently, since $\left\vert \tilde{A}\cap W\right\vert \leq\left\vert
N(\tilde{A})\cap\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right)  -W\right\vert $, we can infer that $\left\vert \tilde
{A}-W\right\vert >\left\vert N(\tilde{A})\cap W\right\vert $. Therefore,
\[
\tilde{A}\cup\left(  W-N(\tilde{A})\right)  =W\cup\left(  \tilde{A}-W\right)
-\left(  N(\tilde{A})\cap W\right)
\]
is an independent set of size greater than $\left\vert W\right\vert
=\alpha\left(  G\right)  $, which is a contradiction that proves the claim.

\emph{(ii)} By part \emph{(i)}, there exists a matching from $S-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda$ into $%
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-S$. Since $X$ is independent, there are no edges between
\[
\left(  S-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\right)  -\left(  S-X\right)  =\left(  S\cap X\right)  -%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\text{ and }X-S.
\]
Therefore, there exists a matching
\[
\text{from }\left(  S\cap X\right)  -%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\text{ into }\left(
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-S\right)  -\left(  X-S\right)  =%
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-\left(  X\cup S\right)  ,
\]
as claimed.
\end{proof}

\begin{figure}[ht]
\setlength{\unitlength}{1cm}\begin{picture}(5,1.8)\thicklines
\multiput(5,0.5)(1,0){6}{\circle*{0.29}}
\multiput(4,1.5)(1,0){4}{\circle*{0.29}}
\multiput(3,0.5)(0,1){2}{\circle*{0.29}}
\put(9,1.5){\circle*{0.29}}
\put(3,0.5){\line(1,0){7}}
\put(3,1.5){\line(2,-1){2}}
\put(4,1.5){\line(1,-1){1}}
\put(4,1.5){\line(1,0){1}}
\put(5,0.5){\line(0,1){1}}
\put(5,0.5){\line(1,1){1}}
\put(6,1.5){\line(1,0){1}}
\put(7,0.5){\line(0,1){1}}
\put(9,0.5){\line(0,1){1}}
\put(9,1.5){\line(1,-1){1}}
\put(3,0.1){\makebox(0,0){$v_{1}$}}
\put(2.65,1.5){\makebox(0,0){$v_{2}$}}
\put(3.65,1.5){\makebox(0,0){$v_{3}$}}
\put(5.35,1.5){\makebox(0,0){$v_{4}$}}
\put(5,0.1){\makebox(0,0){$v_{5}$}}
\put(6,0.1){\makebox(0,0){$v_{6}$}}
\put(6,1.15){\makebox(0,0){$v_{7}$}}
\put(7,0.1){\makebox(0,0){$v_{9}$}}
\put(7.35,1.5){\makebox(0,0){$v_{8}$}}
\put(8.6,1.5){\makebox(0,0){$v_{12}$}}
\put(8,0.1){\makebox(0,0){$v_{10}$}}
\put(9,0.1){\makebox(0,0){$v_{11}$}}
\put(10,0.1){\makebox(0,0){$v_{13}$}}
\put(2,1){\makebox(0,0){$G$}}
\end{picture}\caption{$\left\{  v_{1},v_{2},v_{3},v_{6},v_{8},v_{10}%
,v_{12}\right\}  $, $\left\{  v_{1},v_{2},v_{4},v_{6},v_{7},v_{10}%
,v_{13}\right\}  $,  $\left\{  v_{1},v_{2},v_{4},v_{6},v_{7},v_{10}%
,v_{12}\right\}  $ are maximum independent sets.}%
\label{fig51}%
\end{figure}

\begin{example}
Let us consider the graph $G$ from Figure \ref{fig51} and $S=\left\{
v_{1},v_{4},v_{7}\right\}  \in\mathrm{Ind}(G)$, $\Lambda=\left\{  S_{1}%
,S_{2}\right\}  $, where $S_{1}=\left\{  v_{1},v_{2},v_{3},v_{6},v_{8}%
,v_{10},v_{12}\right\}  $ and $S_{2}=\left\{  v_{1},v_{2},v_{4},v_{6}%
,v_{7},v_{10},v_{13}\right\}  $. Then there is a matching from $S-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda=\left\{  v_{4},v_{7}\right\}  $ into $%
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-S=$ $\left\{  v_{2},v_{3},v_{6},v_{8},v_{10},v_{12},v_{13}\right\}  $,
namely, $M=\left\{  v_{3}v_{4},v_{7}v_{8}\right\}  $.
\end{example}

\begin{remark}
The conclusions of the Matching Lemma may be false, if the family $\Lambda$ is
not included in $\Omega\left(  G\right)  $. Note that in Figure \ref{fig51},
if $S=\left\{  v_{1},v_{2},v_{4},v_{7},v_{9},v_{12}\right\}  \in
\mathrm{Ind}(G)$, $\Lambda=\left\{  S_{1},S_{2}\right\}  $, where
$S_{1}=\left\{  v_{2},v_{3},v_{7}\right\}  $ and $S_{2}=\left\{  v_{1}%
,v_{2},v_{4},v_{6},v_{7},v_{10},v_{12}\right\}  $, then there is no matching
from $S-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda=\left\{  v_{1},v_{4},v_{9},v_{12}\right\}  $ into $%
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-S=$ $\left\{  v_{3},v_{6},v_{10}\right\}  $.
\end{remark}

The Matching Lemma allows us to give an alternative proof of the following
result\ due to Berge.

\begin{lemma}
[\textit{Maximum Stable Set Lemma}]\cite{Berge1981,Berge1985} An independent
set $X$ is maximum if and only if every independent set $S$ disjoint from $X$
can be matched into $X$.
\end{lemma}

\begin{proof}
The \textquotedblleft\textit{only if}\textquotedblright\ part follows from the
Matching Lemma \emph{(i)}, by taking $\Lambda=\left\{  X\right\}  $.

For the \textquotedblleft\textit{if}\textquotedblright\ part we proceed as
follows. According to the hypothesis, there is a matching from $S-X=S-S\cap X$
into $X$, in fact, into $X-S\cap X$, for each $S\in\mathrm{Ind}(G)$. Let
$S\in\Omega\left(  G\right)  $. Hence, we obtain
\[
\alpha\left(  G\right)  =\left\vert S\right\vert =\left\vert S-X\right\vert
+\left\vert S\cap X\right\vert \leq\left\vert X-S\cap X\right\vert +\left\vert
S\cap X\right\vert =\left\vert X\right\vert \leq\alpha\left(  G\right)  ,
\]
which clearly implies $X\in\Omega\left(  G\right)  $.
\end{proof}

Applying the Matching Lemma \emph{(i)} to $\Lambda=\Omega(G)$ we immediately
obtain the following.

\begin{corollary}
\label{cor1}\cite{BorosGolLev2002} For every $S\in\Omega(G)$, there is a
matching from $S-\mathrm{core}(G)$ into $\mathrm{corona}(G)-S$.
\end{corollary}

The following inequality is a numerical interpretation of the Matching Lemma.

\begin{lemma}
[\textit{Set and Collection Lemma}]If $S\in\mathrm{Ind}(G)$, $\Lambda
\subseteq\Omega(G)$, and $\left\vert \Lambda\right\vert \geq1$, then
\[
\left\vert S\right\vert +\alpha(G)\leq\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\cap S\right\vert +\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\cup S\right\vert .
\]

\end{lemma}

\begin{proof}
Let $X\in\Lambda$. By the Matching Lemma \emph{(ii)}, there is a matching from
$S\cap X-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda$ into $%
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-\left(  X\cup S\right)  $. Hence we infer that
\begin{gather*}
\left\vert S\cap X\right\vert -\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\cap S\right\vert =\left\vert S\cap X\right\vert -\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\cap S\cap X\right\vert \\
=\left\vert S\cap X-%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\right\vert \leq\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda-\left(  X\cup S\right)  \right\vert \\
=\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\cup\left(  X\cup S\right)  \right\vert -\left\vert X\cup S\right\vert
=\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\cup S\right\vert -\left\vert X\cup S\right\vert .
\end{gather*}
Therefore, we obtain
\[
\left\vert S\cap X\right\vert -\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\cap S\right\vert \leq\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\cup S\right\vert -\left\vert X\cup S\right\vert ,
\]
which implies%
\[
\left\vert S\right\vert +\alpha\left(  G\right)  =\left\vert S\right\vert
+\left\vert X\right\vert =\left\vert S\cap X\right\vert +\left\vert X\cup
S\right\vert \leq\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\cap S\right\vert +\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\cup S\right\vert ,
\]
as claimed.
\end{proof}

The conclusions of the Set and Collection Lemma may be false, if the family
$\Lambda$ is not included in $\Omega\left(  G\right)  $. For instance, the
graph $G$ of Figure \ref{fig51} has $\alpha\left(  G\right)  =7$, and if
$S=\left\{  v_{1},v_{2},v_{4},v_{7},v_{9},v_{12}\right\}  \in\mathrm{Ind}(G)$,
$\Lambda=\left\{  S_{1},S_{2}\right\}  $, where $S_{1}=\left\{  v_{2}%
,v_{3},v_{7}\right\}  $ and $S_{2}=\left\{  v_{1},v_{2},v_{4},v_{6}%
,v_{7},v_{10},v_{12}\right\}  $, then
\[
13=\left\vert S\right\vert +\alpha(G)\nleqslant\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\cap S\right\vert +\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\cup S\right\vert =11.
\]


\begin{corollary}
\label{cor3}If $\Lambda\subseteq\Omega(G),\left\vert \Lambda\right\vert \geq
1$, then $2\cdot\alpha(G)\leq\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\right\vert +\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right\vert $.
\end{corollary}

\begin{proof}
Let $S\in\Lambda$. Using the Set and Collection Lemma, we obtain%
\[
2\cdot\alpha\left(  G\right)  =\left\vert S\right\vert +\alpha\left(
G\right)  \leq\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\cap S\right\vert +\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\cup S\right\vert =\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\right\vert +\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right\vert ,
\]
as required.
\end{proof}

Since every maximum clique of $G$ is a maximum independent set of
$\overline{G}$, Corollary \ref{cor3} is equivalent to the following result,
due to Hajnal.

\begin{lemma}
[\textit{Clique Collection Lemma}]\cite{Hajnal1965} If $\Gamma$ is a
collection of maximum cliques in $G$, then
\[
\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Gamma\right\vert \geq2\cdot\omega(G)-\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Gamma\right\vert .
\]

\end{lemma}

If $\Lambda=\Omega(G)$, then Corollary \ref{cor3} implies the following.

\begin{corollary}
\label{cor2}For every graph $G$, it is true that
\[
2\cdot\alpha(G)\leq\left\vert \mathrm{core}(G)\right\vert +\left\vert
\mathrm{corona}(G)\right\vert .
\]

\end{corollary}

The graph $G_{1}$ from Figure \ref{Fig55} satisfies $2\cdot\alpha
(G_{1})<\left\vert \mathrm{core}(G_{1})\right\vert +\left\vert \mathrm{corona}%
(G_{1})\right\vert $, because $\alpha\left(  G_{1}\right)  =4$, \textrm{core}%
$\left(  G_{1}\right)  =\{v_{8},v_{9}\}$, and \textrm{corona}$\left(
G_{1}\right)  =\left\{  v_{1},v_{3},v_{4},v_{5},v_{7},v_{8},v_{9}\right\}  $.

\begin{figure}[ht]
\setlength{\unitlength}{1cm}\begin{picture}(5,1.95)\thicklines
\multiput(2,0.5)(1,0){2}{\circle*{0.29}}
\multiput(5,0.5)(1,0){2}{\circle*{0.29}}
\multiput(2,1.5)(1,0){5}{\circle*{0.29}}
\put(2,0.5){\line(1,0){4}}
\put(2,0.5){\line(0,1){1}}
\put(2,1.5){\line(1,0){1}}
\put(2,0.5){\line(1,1){1}}
\put(2,1.5){\line(1,-1){1}}
\put(3,0.5){\line(0,1){1}}
\put(3,0.5){\line(1,1){1}}
\put(3,0.5){\line(2,1){2}}
\put(4,1.5){\line(1,0){1}}
\put(5,0.5){\line(0,1){1}}
\put(5,0.5){\line(1,1){1}}
\put(2,0.1){\makebox(0,0){$v_{1}$}}
\put(3,0.1){\makebox(0,0){$v_{2}$}}
\put(2,1.85){\makebox(0,0){$v_{3}$}}
\put(3,1.85){\makebox(0,0){$v_{4}$}}
\put(4,1.85){\makebox(0,0){$v_{5}$}}
\put(5,0.1){\makebox(0,0){$v_{6}$}}
\put(5,1.85){\makebox(0,0){$v_{7}$}}
\put(6,1.85){\makebox(0,0){$v_{8}$}}
\put(6,0.1){\makebox(0,0){$v_{9}$}}
\put(1,1){\makebox(0,0){$G_{1}$}}
\multiput(9,0.5)(2,0){2}{\circle*{0.29}}
\multiput(12,0.5)(0,1){2}{\circle*{0.29}}
\multiput(9,1.5)(1,0){3}{\circle*{0.29}}
\put(9,0.5){\line(1,0){3}}
\put(9,1.5){\line(1,0){2}}
\put(9,0.5){\line(0,1){1}}
\put(9,0.5){\line(1,1){1}}
\put(9,0.5){\line(2,1){2}}
\put(9,1.5){\line(2,-1){2}}
\put(10,1.5){\line(1,-1){1}}
\put(11,0.5){\line(0,1){1}}
\put(12,0.5){\line(0,1){1}}
\put(9,0.1){\makebox(0,0){$u_{1}$}}
\put(11,0.1){\makebox(0,0){$u_{5}$}}
\put(10,1.85){\makebox(0,0){$u_{3}$}}
\put(11,1.85){\makebox(0,0){$u_{4}$}}
\put(9,1.85){\makebox(0,0){$u_{2}$}}
\put(12,0.1){\makebox(0,0){$u_{6}$}}
\put(12,1.85){\makebox(0,0){$u_{7}$}}
\put(8,1){\makebox(0,0){$G_{2}$}}
\end{picture}\caption{Both $G_{1}$ and $G_{2}$ satsify Corollary \ref{cor2}.}%
\label{Fig55}%
\end{figure}

The \textit{vertex covering number} of $G$, denoted by $\tau(G)$, is the
number of vertices in a minimum vertex cover in $G$, that is, the size of any
smallest vertex cover in $G$. Thus we have $\alpha(G)+\tau(G)=\left\vert
V\left(  G\right)  \right\vert $. Since
\[
\left\vert V\left(  G\right)  \right\vert -\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\left\{  S:S\in\Omega(G)\right\}  \right\vert =\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\left\{  V\left(  G\right)  -S:S\in\Omega(G)\right\}  \right\vert ,
\]
Corollary \ref{cor2} immediately implies the following.

\begin{corollary}
\cite{GitVal2006} If $G$ is a graph, then
\[
\alpha(G)-\left\vert \mathrm{core}(G)\right\vert \leq\tau(G)-|%
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\left\{  V\left(  G\right)  -S:S\in\Omega(G)\right\}  |.
\]

\end{corollary}

It is clear that $\left\vert \mathrm{core}(G)\right\vert +\left\vert
\mathrm{corona}(G)\right\vert \leq\alpha\left(  G\right)  +\left\vert V\left(
G\right)  \right\vert $.

\begin{proposition}
\label{prop2}If $G$ is a graph with a nonempty edge set, then
\[
\left\vert \mathrm{core}(G)\right\vert +\left\vert \mathrm{corona}%
(G)\right\vert \leq\alpha\left(  G\right)  +\left\vert V\left(  G\right)
\right\vert -1.
\]

\end{proposition}

\begin{proof}
Assume, to the contrary, that $\left\vert \mathrm{core}(G)\right\vert
+\left\vert \mathrm{corona}(G)\right\vert \geq\alpha\left(  G\right)
+\left\vert V\left(  G\right)  \right\vert $. 

If $S\in\Omega(G)$, then
\[
\left\vert \mathrm{corona}(G)-S\right\vert =\left\vert \mathrm{corona}%
(G)\right\vert -\alpha\left(  G\right)  \geq\left\vert V\left(  G\right)
\right\vert -\left\vert \mathrm{core}(G)\right\vert =\left\vert V\left(
G\right)  -\mathrm{core}(G)\right\vert .
\]


Since, clearly, $\mathrm{corona}(G)-S\subseteq V\left(  G\right)
-\mathrm{core}(G)$, we obtain $V\left(  G\right)  =\mathrm{corona}(G)$ and
$\mathrm{core}(G)=S$. It follows that $N\left(  \mathrm{core}(G)\right)
=\emptyset$, since $\mathrm{corona}(G)\cap N\left(  \mathrm{core}(G)\right)
=\emptyset$.

On the other hand, since $G$ has a nonempty edge set and $S$ is a maximum
independent set, we have $\emptyset\neq N\left(  S\right)  =N\left(
\mathrm{core}(G)\right)  $.

This contradiction proves the claimed inequality.
\end{proof}

\begin{remark}
The complete bipartite graph $K_{1,n-1}$ satisfies $\alpha\left(
K_{1,n-1}\right)  =n-1$, and hence
\[
\left\vert \mathrm{core}(K_{1,n-1})\right\vert +\left\vert \mathrm{corona}%
(K_{1,n-1})\right\vert =2\left(  n-1\right)  =\alpha\left(  G\right)
+\left\vert V\left(  K_{1,n-1}\right)  \right\vert -1.
\]
In other words, the bound in Proposition \ref{prop2} is tight.
\end{remark}

It has been shown in \cite{LevMan2006} that
\[
\alpha(G)+\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\left\{  V-S:S\in\Omega(G)\right\}  \right\vert =\mu\left(  G\right)
+\left\vert \mathrm{core}(G)\right\vert
\]
is satisfied by every K\"{o}nig-Egerv\'{a}ry graph\textit{ }$G$, and taking
into account that
\[
\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\left\{  V-S:S\in\Omega(G)\right\}  \right\vert =\left\vert V\left(  G\right)
\right\vert -\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\left\{  S:S\in\Omega(G)\right\}  \right\vert ,
\]
we infer that the K\"{o}nig-Egerv\'{a}ry graphs enjoy the following.

\begin{proposition}
\label{prop1}If $G$ is a \textit{K\"{o}nig-Egerv\'{a}ry graph}, then
\[
2\cdot\alpha(G)=\left\vert \mathrm{core}(G)\right\vert +\left\vert
\mathrm{corona}(G)\right\vert .
\]

\end{proposition}

The converse of Proposition \ref{prop1} is not true. For instance, see the
graph $G_{2}$ from Figure \ref{Fig55}, which has $\alpha\left(  G_{2}\right)
=3$, \textrm{corona}$\left(  G_{2}\right)  =\left\{  u_{2},u_{4},u_{6}%
,u_{7}\right\}  $, and \textrm{core}$\left(  G_{2}\right)  =\left\{
u_{2},u_{4}\right\}  $.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions}

In this paper we have proved the \textquotedblleft\textit{Set and Collection
Lemma}\textquotedblright, which has been employed in order to obtain a number
of alternative proofs and/or strengthenings of some known results.

By Proposition \ref{prop1} we know that $2\cdot\alpha(G)=\left\vert
\mathrm{core}(G)\right\vert +\left\vert \mathrm{corona}(G)\right\vert $ holds
for every K\"{o}nig-Egerv\'{a}ry graph\textit{ }$G$. Therefore, it is true for
each very well-covered graph $G$ \cite{LevMan1998}. Recall that $G$ is a
\textit{very well-covered} graph if it has no isolated vertices,
$2\alpha(G)=\left\vert V\left(  G\right)  \right\vert $, and all its maximal
independent sets are of the same cardinality \cite{Favaron1982}. It is worth
noting that there are other graphs enjoying this equality, e.g., every graph
$G$ having a unique maximum independent set, because, in this case,
$\alpha(G)=\left\vert \mathrm{core}(G)\right\vert =\left\vert \mathrm{corona}%
(G)\right\vert $.

\begin{problem}
Characterize graphs satisfying $2\cdot\alpha(G)=\left\vert \mathrm{core}%
(G)\right\vert +\left\vert \mathrm{corona}(G)\right\vert $.
\end{problem}

Let us consider a dual problem. It is clear that for every graph $G$ there
exists a collection of maximum independent sets $\Lambda$ such that
$2\cdot\alpha(G)=\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right\vert +\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\right\vert $. Just take $\Lambda=\left\{  X\right\}  $ for some
maximum independent set $X$.

\begin{problem}
For a given graph $G$ find the cardinality of a largest collection of maximum
independent sets $\Lambda$ such that $2\cdot\alpha(G)=\left\vert
%TCIMACRO{\dbigcup }%
%BeginExpansion
{\displaystyle\bigcup}
%EndExpansion
\Lambda\right\vert +\left\vert
%TCIMACRO{\dbigcap }%
%BeginExpansion
{\displaystyle\bigcap}
%EndExpansion
\Lambda\right\vert $.
\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
We express our special gratitude to Pavel Dvorak for pointing out a gap in the
proof of Lemma \ref{MatchLem}. We also wish to thank the anonymous referees
for a very careful reading of the paper, which resulted in a clearer
presentation of our findings.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

\begin{thebibliography}{10}

\bibitem {Berge1981}C. Berge, Some common properties for regularizable
graphs, edge-critical graphs and $B$-graphs, \emph{Lecture Notes in Computer
Science} \textbf{108} (1981) 108-123.

\bibitem {Berge1985}C. Berge, \emph{Graphs}, North-Holland, New York, 1985.

\bibitem {BorosGolLev2002}E. Boros, M. C. Golumbic, V. E. Levit, On the
number of vertices belonging to all maximum stable sets of a graph, \emph{Discrete
Applied Mathematics} \textbf{124} (2002) 17-25.

\bibitem {CEK2011}D. Christofides, K. Edwardsy, A. D. King, A note on
hitting maximum and maximal cliques with a stable set, \emph{Journal of Graph
Theory} \textbf{73} (2013) 354-360.

\bibitem {Dem1979}R. W. Deming, Independence numbers of graphs - an
extension of the K\"{o}nig-Egerv\'{a}ry theorem, \emph{Discrete Mathematics}
\textbf{27} (1979) 23--33.

\bibitem {Favaron1982}O. Favaron, Very well-covered graphs, \emph{Discrete
Mathematics} \textbf{42} (1982) 177-187.

\bibitem {GitVal2006}I. Gitler, C. E. Valencia, On bounds for the
stability number of graphs, \emph{Morfismos} \textbf{10} (2006) 41-58.

\bibitem {Hajnal1965}A. Hajnal, A theorem on $k$-saturated
graphs, \emph{Canadian Journal of Mathematics} \textbf{10} (1965) 720-724.

\bibitem {King2011}A. D. King, Hitting all maximum cliques with a stable
set using lopsided independent transversals, \emph{Journal of Graph Theory}
\textbf{67} (2011) 300-305.

\bibitem {LevMan1998}V. E. Levit, E. Mandrescu, Well-covered and K\"{o}nig-Egerv\'{a}ry graphs, \emph{Congressus Numerantium} \textbf{130}
(1998) 209-218.

\bibitem {LevMan2002a}V. E. Levit, E. Mandrescu, Combinatorial
properties of the family of maximum stable sets of a graph, \emph{Discrete Applied
Mathematics} \textbf{117} (2002) 149-161.

\bibitem {LevMan2006}V. E. Levit, E. Mandrescu, On $\alpha
$-critical edges in K\"{o}nig-Egerv\'{a}ry graphs, \emph{Discrete
Mathematics} \textbf{306} (2006) 1684-1693.

\bibitem {Rabern2011}L. Rabern, On hitting all maximum cliques with an
independent set, \emph{Journal of Graph Theory} \textbf{66} (2011) 32-37.

\bibitem {Ster1979}F. Sterboul, A characterization of the graphs in
which the transversal number equals the matching number, \emph{Journal of
Combinatorial Theory Series B} \textbf{27} (1979) 228-229.

\end{thebibliography}

\end{document}
