Let \(\alpha(G)\) and \(\mu(G)\) denote the cardinality of a maximum independentset and the size of a maximum matching, respectively, in the graph \(G= (V,E) \) . If \(\alpha(G)+\mu(G)= \lvert V \rvert \) , then G is aKőnig–Egerváry graph.
The number \(d (G) =\max\{ \lvert A \rvert - \lvertN (A) \rvert :A\subseteq V\}\) is the criticaldifference of the graph G, where \(N (A) =\left\{ v:v\inV,N (v) \cap A\neq\emptyset\right\} \) . Every set \(B\subseteq V\) satisfying \(d (G) = \lvert B \rvert - \lvert N (B) \rvert \) is critical. Let \(\varepsilon (G) = \lvert \mathrm{\ker}(G) \rvert \) and \(\xi (G) = \lvert \mathrm{core} (G) \rvert \) , where \(\mathrm{\ker}(G)\) is the intersection of all critical independent sets, and \( \mathrm{core} (G) \) is the intersection of all maximum independent sets. Itis known that \(\mathrm{\ker}(G)\subseteq\) \( \mathrm{core} (G) \) holds for every graph.
Let us define \(\varrho_{v} (G) = \lvert \{ v\in V:G-v \) is a Kőnig–Egerváry graph \(\} \rvert \) ;
\(\varrho_{e} (G) = \lvert \{ e\in E:G-e \) is a Kőnig–Egerváry graph \( \} \rvert \) .
Clearly, \(\varrho_{v} (G) = \lvert V \rvert \) and \(\varrho_{e} (G) = \lvert E \rvert \) for bipartite graphs.Unlike the bipartiteness, the property of being a Kőnig–Egerváry graphis not hereditary.
In this paper, we show that \(\varrho_{v} (G) = \lvert V \rvert -\xi (G) +\varepsilon (G)\phantom{a} \phantom{a}\text{and}\phantom{a} \phantom{a} \varrho_{e} (G) \geq \lvert E \rvert -\xi (G) +\varepsilon (G)\) for every Kőnig–Egerváry graph G.
