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

NEW

Problem: For finite simple graphs, reconstruct Problem 5.4 as follows. Let $G$ be a König-Egerváry graph, i.e.

$$\alpha(G)+\mu(G)=|V(G)|.$$

Let $\rho_e(G)$ be the number of edges $e$ such that $G-e$ is König-Egerváry, $m(G)=|E(G)|$, $\operatorname{core}(G)$ the intersection of all maximum independent sets, and $\ker(G)$ the intersection of all critical independent sets. Characterize those König-Egerváry graphs $G$ for which

$$\rho_e(G)=m(G)\quad\Longrightarrow\quad \operatorname{core}(G)=\ker(G).$$

Result: Let

$$C=\operatorname{core}(G),\qquad K=\ker(G),$$

and define the bipartite graph

$$B_G:=G\big[(C-K),\,N(C)-N(K)\big],$$

whose edges are precisely the edges of $G$ joining $C-K$ to $N(C)-N(K)$.

Then $G$ satisfies

$$\rho_e(G)=m(G)\Longrightarrow C=K$$

if and only if either $C=K$, or $B_G$ has an edge contained in every perfect matching of $B_G$.

Equivalently,

$$m(G)-\rho_e(G)$$

is exactly the number of edges of $B_G$ that belong to every perfect matching of $B_G$. Hence $\rho_e(G)=m(G)$ holds exactly when $B_G$ has no such forced edge.

Proof sketch. In a König-Egerváry graph, $C$ and $K$ are critical independent sets, with $K\subseteq C$. Known matching structure gives a perfect matching between $C-K$ and $N(C)-N(K)$. Moreover, every maximum matching of $G$ restricts to a perfect matching of $B_G$, and every perfect matching of $B_G$ extends to a maximum matching of $G$. Therefore an edge of $B_G$ is $\mu$-critical in $G$ exactly when it is contained in every perfect matching of $B_G$.

Edges outside $(C,N(C))$ always preserve the König-Egerváry property after deletion. Also, an edge incident with a core vertex cannot be $\alpha$-critical: if deleting $xy$ with $x\in C$ increased $\alpha$, then a maximum independent set of $G-xy$ containing both $x,y$ would yield a maximum independent set of $G$ avoiding $x$, contradicting $x\in C$. Thus, among edges incident with $C$, deletion fails to preserve the König-Egerváry property exactly for the $\mu$-critical ones. The only possible such edges lie in $B_G$. Hence the non-preserving edges are precisely the forced edges of $B_G$, proving the characterization.

Citation: Uses structural results from V. E. Levit and E. Mandrescu, “On the Number of Vertices/Edges whose Deletion Preserves the König-Egerváry Property,” arXiv:2401.05523, especially Theorems 4.2, 4.5, and 4.8.