% 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}