On the Number of Vertices/Edges whose Deletion Preserves the König-Egerváry Property

NEW

Problem: Reconstructed statement: for a finite simple graph $G$, characterize non-König-Egerváry graphs satisfying each of the three displayed conditions in Problem 5.2. Here $\alpha,\mu,n,m,\operatorname{core},\ker,\xi,\varepsilon,\varrho_v,\varrho_e$ are as in Levit--Mandrescu. Literal simultaneous satisfaction of the second and third equalities is impossible for a non-KE graph, since it would imply $n(G)=\alpha(G)+\mu(G)$.

Result: Let

so $G$ is KE iff $\delta(G)=0$. Let $C=\operatorname{core}(G)$, $K=\ker(G)$, $U=\{v:\mu(G-v)=\mu(G)-1\}$, and let

For a non-KE graph $G$, the exact characterizations are:

iff $G$ is $1$-KE, i.e. $\delta(G)=1$, and

Equivalently, all but at most $\xi(G)-\varepsilon(G)$ edges are $\alpha$-critical but not $\mu$-critical.

iff $\delta(G)=1$, $\varepsilon(G)=0$, and every $\mu$-critical vertex lies in $\operatorname{core}(G)$, i.e. $U\subseteq C$.

iff $\delta(G)=1$ and

Thus either $\varepsilon(G)=0$ and exactly one $\mu$-critical vertex lies outside $C$, or $\varepsilon(G)=1$ and $U\subseteq C$.

Proof sketch. For a vertex $v$, put $a_v=1$ iff $v\in C$, and $b_v=1$ iff $v\in U$. Then

Hence for non-KE $G$, $G-v$ is KE iff $\delta(G)=1$, $v\notin C$, and $v\notin U$. Therefore, when $\delta=1$,

The two vertex characterizations follow immediately.

For an edge $e$, put $c_e=1$ iff $e\in F_\alpha$, and $d_e=1$ iff $e\in F_\mu$. Then

Thus $G-e$ is KE iff $\delta(G)=1$, $e\in F_\alpha$, and $e\notin F_\mu$, giving

for $1$-KE graphs and $0$ otherwise.

Finally, for every non-KE graph, $m-\xi+\varepsilon>0$: since $K\subseteq C$, every vertex of $C\setminus K$ is non-isolated, and choosing one incident edge gives $|C\setminus K|\le m$; equality would force all edges to go between $C\setminus K$ and its complement, making $G$ bipartite and hence KE, contradiction. Thus the edge inequality cannot hold when $\delta>1$.

Verification audit: the proof uses exactly the paper’s finite simple graph setting and introduces only the standard deficiency $\delta=n-\alpha-\mu$, $\alpha/\mu$-critical vertices and edges. The simultaneous reading has no non-KE solutions; the listed theorem resolves the intended separate-bullet reading.

Citation: Problem and notation: Vadim E. Levit and Eugen Mandrescu, “On the Number of Vertices/Edges whose Deletion Preserves the König-Egerváry Property,” arXiv:2401.05523, Problem 5.2. Uses the standard fact $\ker(G)\subseteq\operatorname{core}(G)$ recalled there, and König’s theorem that bipartite graphs are KE.