On \(\alpha\)-critical edges in König--Egerváry graphs (Q2502896)

A set \(S\) of vertices of a finite simple graph \(G\) is stable if no two vertices from \(S\) are adjacent. The stability number \(\alpha(G)\) of \(G\) is the cardinality of a maximum size stable set in \(G\). If \(\alpha(G-e) > \alpha(G)\) then \(e\) is an \(\alpha\)-critical edge. In 1967 it was shown by \textit{L. W. Beineke, F. Harary}, and \textit{M. D. Plummer} [Pac. J. Math. 22, 205--212 (1967; Zbl 0166.19902)] that the set of \(\alpha\)-critical edges of a bipartite graph constitutes a matching. The main result of the present paper is a generalization of this theorem to the effect that it holds also for König-Egerváry graphs. Note that if \(\mu(G)\) is the cardinality of a maximal matching in \(G\) then \(G\) is called a König-Egerváry graph when \(| V(G)| =\alpha(G)+\mu(G)\). That all bipartite graphs are König-Egerváry has been known since the 1930's.