Monotonic properties of collections of maximum independent sets of a graph (Q2314418)

Let \(G\) be a graph. The set \(S\subset V(G)\) is independent if there exists no edges between vertices of \(S\) and \(\alpha(G)\) is the maximum cardinality of an independent set. Let \(\Omega(G)\) denote the family of all maximum independent sets of \(G\) and let \(\Gamma\) be any subfamily of \(\Omega (G)\). The function \(f:\Gamma\mapsto \mathbb{N}\) is defined with \[ f(\Gamma)=\left|\bigcup_{S\in\Gamma}S\right|+\left|\bigcap_{S\in\Gamma}S\right|. \] Two subfamilies \(\Gamma\) and \(\Gamma^\prime\) of \(\Omega(G)\) are in relation \(\triangleleft\), that is \(\Gamma^\prime\triangleleft \Gamma\), if \[ \bigcup_{S^\prime\in\Gamma^\prime}S^\prime\subseteq \bigcup_{S\in\Gamma}S \text{ and } \bigcap_{S\in\Gamma}S\subseteq \bigcap_{S^\prime\in\Gamma^\prime}S^\prime. \] The authors show that \(f\) is \(\triangleleft\)-increasing together with several consequences of that. In particular, they show that the following equation holds for every König-Egerváry graph \(G\): \[ \left|\bigcup_{S\in\Gamma}S\right|+\left|\bigcap_{S\in\Gamma}S\right|=2\alpha(G). \]