Several necessary properties of König–Egerváry graphs involving the core, the corona, and critical independent sets are by now part of the folklore of the theory, and have motivated different lines of research within the same framework. In particular, every König–Egerváry graph satisfies the core–corona identity \(|core(G)|+|corona(G)|=2\alpha(G),\) the covering relation \(corona(G)cup N(core(G))=V(G),\) and the fact that \(core(G)\) is a critical independent set. Each of these conditions captures a different aspect of the interaction between maximum independent sets and matchings, but none of them alone characterizes the König–Egerváry property. In this note we show that their conjunction does: a graph \(G\) is König–Egerváry if and only if the above two core–corona conditions hold and \(core(G)\) is critical. Equivalently, the class of König–Egerváry graphs is precisely the intersection of the three graph families determined by these conditions. We also provide examples showing that the characterization is sharp: any two of the three conditions may hold in a graph which is not König–Egerváry.
Let \(\alpha(G)\) denote the cardinality of a maximum independent set of \(G\), and let \(\mu(G)\) denote the size of a maximum matching of \(G\). Since every edge of a matching must meet the complement of any maximum independent set, one always has \[\alpha(G)+\mu(G)\leq |V(G)|.\]
A graph \(G\) is called a König–Egerváry graph if equality holds, that is, if \[\alpha(G)+\mu(G)=|V(G)|,\] see [3, 6, 24]. König–Egerváry graphs have been extensively studied [2, 7, 8, 9, 13, 14]. It is known that every bipartite graph is a König–Egerváry graph [5]. These graphs were independently introduced by Deming [3], Sterboul [24], and [6].
Let \(\Omega^{*}(G)=\left\{ S:S\text{ is an independent set of }G\right\}\), \(\Omega(G)=\{S:S\) is a maximum independent set of \(G\}\), \(\text{core}(G)=\bigcap\left\{ S:S\in\Omega(G)\right\}\) [12], and \(\text{corona}(G)=\bigcup\left\{ S:S\in\Omega(G)\right\}\) [1]. The number \(d_{G}(X)=\left|X\right|-\left|N(X)\right|\) is the difference of the set \(X\subset V(G)\), and \(d(G)=\max\{d_{G}(X):X\subset V(G)\}\) is called the critical difference of \(G\). A set \(U\subset V(G)\) is critical if \(d_{G}(U)=d(G)\) [25]. The number \(d_{I}(G)=\max\left\{ d_{G}(X):X\in\Omega^{*}(G)\right\}\) is called the critical independence difference of \(G\). If a set \(X\in\Omega^{*}(G)\) satisfies \(d_{G}(X)=d_{I}(G)\), then it is called a critical independent set [25]. Clearly, \(d(G)\ge d_{I}(G)\) holds for every graph. It is known that \(d(G)=d_{I}(G)\) for all graphs [25]. Actually, every critical independent set is contained in a maximum critical independent set, and a maximum critical independent set can be found in polynomial time [10].
It is known that for every König–Egerváry graph \(G\), the sets \(\operatorname{core}(G)\) and \(\operatorname{corona}(G)\) are both critical [16], while for graphs in general this property fails. The graphs for which \(\operatorname{core}(G)\) or \(\operatorname{corona}(G)\) is a critical set have been studied and characterized in [19]. The fact that the core is a critical independent set does not guarantee that the graph is a König–Egerváry graph; for example, consider a \(K_{3}.\)
Every König–Egerváry graph \(G\) satisfies \(\left|\operatorname{core}(G)\right|+\left|\operatorname{corona}(G)\right|=2\alpha(G)\) [15]. It has been of interest to study, in a parametrized way, the graphs for which \(\left|\operatorname{core}(G)\right|+\left|\operatorname{corona}(G)\right|=2\alpha(G)+k\) [23, 22]. In particular, almost–bipartite non–König–Egerváry graphs satisfy \(\left|\operatorname{core}(G)\right|+\left|\operatorname{corona}(G)\right|=2\alpha(G)+1\) [18]. More generally, the equality \(\left|\operatorname{core}(G)\right|+\left|\operatorname{corona}(G)\right|=2\alpha(G)\) for König–Egerváry graphs follows from the following more general fact: a graph is a König–Egerváry graph if and only if \[\left|\bigcap\Gamma\right|+\left|\bigcup\Gamma\right|=2\alpha(G),\] for some (equivalently, for every) \(\emptyset\neq\Gamma\subset\operatorname{MaxCritIndep}(G)\) [17]. This result is known as the König–Egerváry collection theorem, and it has been further generalized in [20]. Notice that not every graph with \(\left|\operatorname{core}(G)\right|+\left|\operatorname{corona}(G)\right|=2\alpha(G)\) is a König–Egerváry graph; for example, consider two copies of \(K_{3}\) with one vertex in common.
A celebrated result in the theory of König–Egerváry graphs shows that \(\operatorname{core}(G)\) and \(\operatorname{corona}(G)\) are strongly related in König–Egerváry graphs in the following way: \[\operatorname{corona}(G)\cup N(\operatorname{core}(G))=V(G),\] see [12]. Later, this property was studied in a more general context in [7]. However, not every graph with this property is a König–Egerváry graph; for example, consider again a \(K_3\).
Individually, however, these conditions do not characterize König–Egerváry graphs. Even taken in pairs they are not sufficient. This raises a natural question: are these three necessary conditions jointly sufficient? The main purpose of this paper is to give an affirmative answer. More precisely, we prove that a graph \(G\) is König–Egerváry if and only if the following three conditions hold simultaneously: \[|\operatorname{core}(G)|+|\operatorname{corona}(G)|=2\alpha(G),\] \[\operatorname{corona}(G)\cup N(\operatorname{core}(G))=V(G),\] and \(\operatorname{core}(G)\) is a critical independent set. Equivalently, if \(\mathcal{F}_1\), \(\mathcal{F}_2\), and \(\mathcal{F}_3\) denote the families of graphs satisfying these three respective conditions, then \[\mathcal{F}_1\cap\mathcal{F}_2\cap\mathcal{F}_3,\] is exactly the class of König–Egerváry graphs.
The contribution should be understood in this precise sense. We do not claim a replacement for the Larson–Levit–Mandrescu characterization, nor for the König–Egerváry collection theorem. Rather, we isolate an intrinsic criterion expressed by the canonical pair \((\operatorname{core}(G),\operatorname{corona}(G))\) and the criticality of the core. The collection theorem concerns arbitrary nonempty subcollections of maximum critical independent sets, whereas the present theorem uses only the intersection and union of maximum independent sets and identifies exactly which additional critical-difference condition turns the two standard core–corona properties into the König–Egerváry equality. Thus the theorem gives a compact recognition criterion once \(\operatorname{core}(G)\), \(\operatorname{corona}(G)\), and \(d(\operatorname{core}(G))\) are known, and Section 5 shows that none of these three natural hypotheses can be omitted.
The proof is based on the critical independent-set characterization of König–Egerváry graphs due to Larson and Levit–Mandrescu [11, 14]. We also use a matching form of this characterization for maximum independent sets. Namely, if \(S\in\Omega(G)\) and \(T=V(G)-S\), then \(S\) is critical if and only if there exists a matching from \(T\) into \(S\) saturating every vertex of \(T\). This matching certificate is important for the core–corona argument, because it allows us to translate criticality into an explicit comparison between \(\operatorname{corona}(G)-S\) and \(S-\operatorname{core}(G)\), and later to recover the equality \[\mu(G)=|V(G)|-\alpha(G).\]
Finally, we show that the characterization is sharp. For each pair among the three conditions above, we construct a graph satisfying that pair and failing the remaining condition, while not being König–Egerváry. Hence none of the three hypotheses can be omitted.
The note is organized as follows. Section 2 contains the basic terminology and notation. In Section 3 we prove preliminary results. Section 4 establishes the core–corona characterization of König–Egerváry graphs. Section 5 gives the pairwise sharpness examples. We conclude in Section 6 with some final remarks.
All graphs considered in this paper are finite, undirected, and simple. For any undefined terminology or notation, we refer the reader to Lovász and Plummer [21] or Diestel [4].
Let \(G = (V, E)\) be a simple graph, where \(V = V(G)\) is the finite set of vertices and \(E = E(G)\) is the set of edges, with \(E \subseteq \{\{u, v\} : u, v \in V, u \neq v\}\). We denote the edge \(e=\{u, v\}\) as \(uv\). A subgraph of \(G\) is a graph \(H\) such that \(V(H) \subseteq V(G)\) and \(E(H) \subseteq E(G)\). A subgraph \(H\) of \(G\) is called a spanning subgraph if \(V(H) = V(G)\). For two vertex sets \(X,Y\subseteq V(G)\), we denote by \(E(X,Y)\) the set of edges \(uv\in E(G)\) such that \(u\in X\) and \(v\in Y\). The number of vertices in a graph \(G\) is called the order of the graph and denoted by \(\left|G\right|\).
Let \(e \in E(G)\) and \(v \in V(G)\). We define \(G – e := (V, E – \{e\})\) and \(G – v := (V – \{v\}, \{uw \in E : u,w \neq v\})\). If \(X \subseteq V(G)\), the induced subgraph of \(G\) by \(X\) is the subgraph \(G[X]=(X,F)\), where \(F:=\{uv \!\in\! E(G) : u, v \!\in \! X\}\). The union of two graphs \(G\) and \(H\) is the graph \(G\cup H\) with \(V(G\cup H)=V(G)\cup V(H)\) and \(E(G\cup H)=E(G)\cup E(H)\). If \(M\) is a set of edges of \(G\), we denote by \(G[M]\) the subgraph of \(G\) spanned by the edges of \(M\), that is, \(V(G[M])=\{v\in V(G): \text{$v$ is an endpoint of some edge in } M\}\) and \(E(G[M])=M.\)
For a vertex \(v\in V(G)\), its open neighborhood is \[N_G(v)=\{u\in V(G):uv\in E(G)\}.\]
For a set \(X\subseteq V(G)\), we write \[N_G(X)=\{u\in V(G)-X:\text{ there exists }x\in X \text{ such that }ux\in E(G)\}.\]
When no confusion is possible, we write \(N(v)\) and \(N(X)\) instead of \(N_G(v)\) and \(N_G(X)\).
A matching \(M\) in a graph \(G\) is a set of pairwise non-adjacent edges. The matching number of \(G\), denoted by \(\mu(G)\), is the maximum cardinality of any matching in \(G\). A vertex is saturated by \(M\) if it is incident with an edge of \(M\). We shall also use the usual mate notation: if \(uv\in M\), then \(M(u)=v\) and \(M(v)=u\). Unmatched vertices are left undefined for this notation unless explicitly stated otherwise. If \(S,U\subseteq V(G)\) are disjoint, a matching from \(S\) into \(U\) means a matching that saturates every vertex of \(S\) and whose mate of each vertex of \(S\) belongs to \(U\); equivalently, it induces an injective map from \(S\) to \(U\). A matching \(M\) is perfect if it saturates every vertex of the graph. A vertex set \(S \subseteq V\) is independent if, for every pair of vertices \(u, v \in S\), we have \(uv \notin E\). The number of vertices in a maximum independent set is denoted by \(\alpha(G)\).
Before proving the main characterization, we collect the critical independent-set tools that translate the core–corona information into a matching statement. The first one is a standard consequence of Hall’s theorem.
Lemma 3.1 ([10]). Let \(G\) be a graph and \(I\) a critical independent set of \(G\). Then there exists a maximum matching of \(G\) that matches the vertices \(N(I)\) into (a subset of) the vertices of \(I\).
We also need the following elementary observation.
Lemma 3.2. For every graph \(G\), \[N(\operatorname{core}(G))\cap \operatorname{corona}(G)=\varnothing.\]
Proof. Let \(x\in\operatorname{corona}(G)\). Then \(x\in S\) for some \(S\in\Omega(G)\). Since \(\operatorname{core}(G)\subseteq S\) and \(S\) is independent, \(x\) is not adjacent to any vertex of \(\operatorname{core}(G)\). Hence \(x\notin N(\operatorname{core}(G))\). \(\square\)
The first three conditions in the next statement form a known characterization of König–Egerváry graphs due to Larson and Levit–Mandrescu [11, 14]. Only this equivalence is imported from those papers. We include the fourth condition in the same formulation because it is the numerical trace of the same critical independence phenomenon, and the equivalence with the first three conditions follows immediately from the definitions. Indeed, every maximum independent set has the same difference value \(2\alpha(G)-|V(G)|\); hence asking such a set to be critical is equivalent to asking the whole graph to attain this value.
Theorem 3.3 (Larson; Levit–Mandrescu). For every graph \(G\), the following assertions are equivalent:
(a) \(G\) is a König–Egerváry graph;
(b) some maximum independent set of \(G\) is critical;
(c) every maximum independent set of \(G\) is critical;
(d) \(d(G)=2\alpha(G)-|V(G)|.\)
Proof. The equivalence between the first three assertions is exactly the theorem of Larson and Levit–Mandrescu [11, 14], and is not reproved here. It remains only to explain why the fourth assertion is equivalent to the criticality of maximum independent sets.
Let \(S\in\Omega(G)\). Since \(S\) is a maximum independent set, it is maximal; therefore \[N(S)=V(G)- S.\]
Consequently, \[\begin{aligned} d(S) =& |S|-|N(S)| \\[1mm] =& \alpha(G)-\bigl(|V(G)|-\alpha(G)\bigr) \\[1mm] =& 2\alpha(G)-|V(G)|. \end{aligned}\]
Thus every maximum independent set has difference exactly \(2\alpha(G)-|V(G)|\). Hence some maximum independent set is critical if and only if \[d(G)=2\alpha(G)-|V(G)|.\]
Equivalently, the same equality holds if and only if every maximum independent set is critical. This proves the equivalence with the fourth assertion. \(\square\)
Lemma 3.1 takes the following form for maximum independent sets. In this form, it is possible to obtain the converse of the result in the following sense.
Lemma 3.4. Let \(S\in\Omega(G)\) and let \(T=V(G)- S\). Then \(S\) is critical if and only if there exists a matching from \(T\) into \(S\), that is, a matching that saturates all vertices of \(T\).
Proof. If \(I\) is a critical independent set, then by Lemma 3.1 there exists a matching from \(N(I)\) into \(I\).
Applying this to \(I=S\), since \(S\) is a maximum independent set, it is also maximal; hence \[N(S)=V(G)- S=T.\]
Thus, there exists a matching from \(T\) into \(S\).
Conversely, suppose that there exists a matching \(M\) that saturates \(T\) in \(S\). Then the function \(M:T\to S\) is injective.
We shall prove that \(d(A)\leq d(S)\) for every independent set \(A\). To follow this part of the proof, see Figure 1.
We write \[A_S=A\cap S, \qquad A_T=A\cap T.\]
If \(t\in A_T\), then \(M(t)\in N(A)\cap S\), since \(t\) is adjacent to \(M(t)\); moreover \(M(t)\notin A\) because \(A\) is independent. Since \(M\) is injective, \[\begin{aligned} |A_T|\leq |N(A)\cap S|. \end{aligned}\tag{1}\]
On the other hand, if \(t\in T- N(A)\), then \(M(t)\notin A_S\); otherwise, \(t\) would be adjacent to a vertex of \(A\). Thus, \[M\bigl(T- N(A)\bigr)\subseteq S- A_S.\]
Again by injectivity, \[|T|-|N(A)\cap T|=|T- N(A)|\leq |S|-|A_S|.\]
Equivalently, \[\begin{aligned} |A_S|-|N(A)\cap T|\leq |S|-|T|. \end{aligned}\tag{2}\]
Using (1) and (2), we obtain \[\begin{aligned} d(A) =&|A|-|N(A)| \\ =&|A_S|+|A_T|-|N(A)\cap S|-|N(A)\cap T| \\ \leq &|A_S|-|N(A)\cap T| \\ \leq &|S|-|T| \\ =&|S|-|N(S)| \\ =&d(S). \end{aligned}\]
Therefore \(d(A)\leq d(S)\) for every independent set \(A\). Hence \(d_I(G)\leq d(S)\). Since \(S\) itself is independent, \(d_I(G)\geq d(S)\), and so \(d_I(G)=d(S)\). By Zhang’s equality \(d(G)=d_I(G)\) for all graphs [25], we obtain \(d(G)=d(S)\). Thus \(S\) is critical. \(\square\)
As mentioned in the abstract, each of the three conditions appearing in Theorem 4.1 is necessary for König–Egerváry graphs, but none of them alone is sufficient to characterize this class. Therefore, although these properties are known to hold for König–Egerváry graphs, we include short proofs for completeness and to show explicitly how the imported Larson–Levit–Mandrescu critical-set characterization is combined with the core–corona information. This also allows us to collect these facts in a unified form and to make the proof of the main characterization self-contained.
Theorem 4.1. Let \(G\) be a finite simple graph. Then \(G\) is a König–Egerváry graph if and only if the following three conditions hold simultaneously:
x(A1) \(|\operatorname{core}(G)|+|\operatorname{corona}(G)|=2\alpha(G)\);
x(A2) \(\operatorname{corona}(G)\cup N(\operatorname{core}(G))=V(G)\);
x(A3) \(\operatorname{core}(G)\) is a critical independent set.
Proof. Assume first that \(G\) is König–Egerváry. Fix \(S\in\Omega(G)\) and set \[T=V(G)- S.\]
By Theorem 3.3, \(S\) is critical. Lemma 3.4 therefore gives a matching \(M\) from \(T\) into \(S\). Thus, for every \(x\in T\), we have \(M(x)\in S\).
We first prove that \(M\) induces a bijection from \(\operatorname{corona}(G)- S\) onto \(S-\operatorname{core}(G)\).
Let \(x\in\operatorname{corona}(G)- S\). Choose \(A\in\Omega(G)\) with \(x\in A\). Since \(x\) is adjacent to \(M(x)\) and \(A\) is independent, \(M(x)\notin A\). Because \(\operatorname{core}(G)\subseteq A\), it follows that \(M(x)\notin\operatorname{core}(G)\). Thus \[M\bigl(\operatorname{corona}(G)- S\bigr)\subseteq S-\operatorname{core}(G).\]
Conversely, let \(y\in S-\operatorname{core}(G)\). Since \(y\notin\operatorname{core}(G)\), there exists \(A\in\Omega(G)\) such that \(y\notin A\). For every \(x\in A- S\), the vertices \(x\) and \(M(x)\) are adjacent, and \(x\in A\); hence \(M(x)\notin A\). Therefore \[M(A- S)\subseteq S- A.\]
Since \(|A|=|S|\), we have \(|A- S|=|S- A|\). The map \(M\) is injective, so \[M(A- S)=S- A.\]
In particular, \(y\in S- A\), and hence \(y=M(x)\) for some \(x\in A- S\). This vertex \(x\) belongs to \(\operatorname{corona}(G)- S\). Hence \[S-\operatorname{core}(G)\subseteq M\bigl(\operatorname{corona}(G)- S\bigr).\tag{3}\]
From (2) and (3), the matching \(M\) gives a bijection \[\operatorname{corona}(G)- S\longleftrightarrow S-\operatorname{core}(G).\]
Thus \[|\operatorname{corona}(G)|-\alpha(G)=\alpha(G)-|\operatorname{core}(G)|,\] and therefore \[|\operatorname{core}(G)|+|\operatorname{corona}(G)|=2\alpha(G).\]
This proves (A1).
We next prove (A2). By Lemma 3.2, \[N(\operatorname{core}(G))\cap\operatorname{corona}(G)=\varnothing,\] then \(N(\operatorname{core}(G))\subseteq V(G)-\operatorname{corona}(G)\). It remains to prove that every vertex outside \(\operatorname{corona}(G)\) lies in \(N(\operatorname{core}(G))\). Let \[x\in V(G)-\operatorname{corona}(G).\]
Since \(S\subseteq\operatorname{corona}(G)\), we have \(x\notin S\). Suppose that \(M(x)\notin\operatorname{core}(G)\). Then \(M(x)\in S-\operatorname{core}(G)\). By the bijection above, there is a vertex \(z\in\operatorname{corona}(G)- S\) such that \(M(z)=M(x)\). Since the map induced by \(M\) is injective on \(V(G)- S\), we get \(z=x\), contradicting \(x\notin\operatorname{corona}(G)\). Hence \(M(x)\in\operatorname{core}(G)\). Since \(x\) is adjacent to \(M(x)\), we have \(x\in N(\operatorname{core}(G))\). Therefore \[V(G)-\operatorname{corona}(G)\subseteq N(\operatorname{core}(G)).\]
Together with Lemma 3.2, this gives \[\operatorname{corona}(G)\cup N(\operatorname{core}(G))=V(G),\] so (A2) holds.
Finally we prove (A3). From (A2) and Lemma 3.2, \[N(\operatorname{core}(G))=V(G)-\operatorname{corona}(G).\]
Using (A1), we get \[\begin{aligned} d(\operatorname{core}(G)) =& |\operatorname{core}(G)|-|N(\operatorname{core}(G))| \\ =& |\operatorname{core}(G)|-\bigl(|V(G)|-|\operatorname{corona}(G)|\bigr) \\ =& |\operatorname{core}(G)|+|\operatorname{corona}(G)|-|V(G)| \\ =& 2\alpha(G)-|V(G)|. \end{aligned}\]
Since \(G\) is König–Egerváry, Theorem 3.3 gives \[d(G)=2\alpha(G)-|V(G)|.\]
Thus \(d(\operatorname{core}(G))=d(G)\), and \(\operatorname{core}(G)\) is critical. This proves (A3).
Conversely, assume that (A1), (A2), and (A3) hold. By Lemma 3.2, condition (A2) implies \[N(\operatorname{core}(G))=V(G)-\operatorname{corona}(G).\]
Therefore, using (A1), \[\begin{aligned} d(\operatorname{core}(G)) =& |\operatorname{core}(G)|-|N(\operatorname{core}(G))| \\ =& |\operatorname{core}(G)|-\bigl(|V(G)|-|\operatorname{corona}(G)|\bigr) \\ =& |\operatorname{core}(G)|+|\operatorname{corona}(G)|-|V(G)| \\ =& 2\alpha(G)-|V(G)|. \end{aligned}\]
By (A3), \(\operatorname{core}(G)\) is critical, so \[d(G)=d(\operatorname{core}(G))=2\alpha(G)-|V(G)|.\]
This is assertion (4) in Theorem 3.3. By the equivalence with assertion (1), which is the Larson–Levit–Mandrescu characterization as recorded in Theorem 3.3, \(G\) is a König–Egerváry graph. \(\square\)
Theorem 4.1 should be read as a core–corona reformulation of the critical independent-set characterization. Condition (A1) is a size identity. Condition (A2) says that the vertices outside the corona are exactly detected by the neighborhood of the core. Condition (A3) says that this same core realizes the critical difference. The proof shows that the three pieces together are precisely what is needed to recover the numerical equality \(d(G)=2\alpha(G)-|V(G)|\) from the canonical pair \((\operatorname{core}(G),\operatorname{corona}(G))\). This distinguishes the result from the König–Egerváry collection theorem, which uses collections of maximum critical independent sets, and from the Larson–Levit–Mandrescu theorem, which is stated in terms of criticality of maximum independent sets. Here the criterion is phrased directly in terms of the core and corona, and the examples in Section 5 show that each of the three core–corona hypotheses is necessary.
We now show that none of the three conditions in Theorem 4.1 can be omitted. For each pair of conditions there exists a graph satisfying that pair and failing the third one, while still not being König–Egerváry.
| Conditions satisfied | Graph | Condition that fails |
|---|---|---|
| (A1) and (A2) | \(K_2\vee (K_2\cup K_1)\) | (A3) |
| (A1) and (A3) | two triangles with exactly one common vertex | (A2) |
| (A2) and (A3) | \(K_4\) with one pendant leaf | (A1) |
Example 5.1 (Conditions (A1) and (A2) do not imply (A3)). Let \[G_1=K_2\vee (K_2\cup K_1).\]
More explicitly, take \[V(G_1)=\{x,y,a,b,z\},\] where \(xy\) is an edge, \(ab\) is an edge, \(z\) is isolated inside \(K_2\cup K_1\), and every vertex in \(\{x,y\}\) is adjacent to every vertex in \(\{a,b,z\}\). Thus \[E(G_1)=\{xy,ab,xa,xb,xz,ya,yb,yz\}.\]
The maximum independent sets of \(G_1\) are exactly \[\Omega(G_1)=\bigl\{\{a,z\},\{b,z\}\bigr\}.\]
Therefore \[\alpha(G_1)=2, \qquad \operatorname{core}(G_1)=\{z\}, \qquad \operatorname{corona}(G_1)=\{a,b,z\}.\]
Moreover, \[N(\operatorname{core}(G_1))=N(\{z\})=\{x,y\}.\]
Consequently, \[\begin{aligned} |\operatorname{core}(G_1)|+|\operatorname{corona}(G_1)| =& 1+3 \\ =& 4 \\ =& 2\alpha(G_1), \end{aligned}\] and \[\begin{aligned} \operatorname{corona}(G_1)\cup N(\operatorname{core}(G_1)) =& \{a,b,z\}\cup\{x,y\} \\ =& V(G_1). \end{aligned}\]
Thus \(G_1\) satisfies (A1) and (A2).
However, \(\operatorname{core}(G_1)\) is not critical. Indeed, \[\begin{aligned} d(\operatorname{core}(G_1)) =& d(\{z\}) \\ =& |\{z\}|-|N(\{z\})| \\ =& 1-2 \\ =& -1, \end{aligned}\] whereas \(d(\emptyset)=0\). Hence \(\operatorname{core}(G_1)\) does not attain the maximum value of the difference function, and (A3) fails.
Finally, \(G_1\) is not König–Egerváry. Since \(|V(G_1)|=5\), every matching has size at most \(2\). The set \(\{xz,ab\}\) is a matching of size \(2\), so \(\mu(G_1)=2\). Thus \[\begin{aligned} \alpha(G_1)+\mu(G_1) =& 2+2 \\ =& 4 \\ <& 5 \\ =& |V(G_1)|. \end{aligned}\]
Therefore \(G_1\) is not a König–Egerváry graph.
Example 5.2 (Conditions (A1) and (A3) do not imply (A2)). Let \(G_2\) be the graph obtained by identifying one vertex of two disjoint triangles. We write the common vertex as \(w\), and the other vertices as \(u_1,u_2,v_1,v_2\). Thus \[V(G_2)=\{u_1,u_2,v_1,v_2,w\},\] and \[E(G_2)=\{u_1u_2,u_1w,u_2w,v_1v_2,v_1w,v_2w\}.\]
The maximum independent sets of \(G_2\) are exactly \[\Omega(G_2)=\bigl\{\{u_i,v_j\}:i,j\in\{1,2\}\bigr\}.\]
Hence \[\alpha(G_2)=2, \qquad \operatorname{core}(G_2)=\emptyset, \qquad \operatorname{corona}(G_2)=\{u_1,u_2,v_1,v_2\}.\]
Therefore \[\begin{aligned} |\operatorname{core}(G_2)|+|\operatorname{corona}(G_2)| =& 0+4 \\ =& 4 \\ =& 2\alpha(G_2), \end{aligned}\] so (A1) holds.
We now check (A3). Since \(\operatorname{core}(G_2)=\emptyset\), we have \(d(\operatorname{core}(G_2))=d(\emptyset)=0\). No nonempty independent set has positive difference. Indeed, every independent set of size \(1\) has at least two neighbors. Also, every independent set of size \(2\) is of the form \(\{u_i,v_j\}\), and its neighborhood consists of \(w\), the other vertex in the \(u\)-triangle, and the other vertex in the \(v\)-triangle; hence its neighborhood has size \(3\). Thus \(d(I)\leq 0\) for every independent set \(I\), so \(d_I(G_2)=0\). Since \(d(G_2)=d_I(G_2)\) [25], we get \(d(G_2)=0\). Hence \(\operatorname{core}(G_2)\) is critical, and (A3) holds.
On the other hand, (A2) fails. Since \(N(\emptyset)=\emptyset\), we get \[\begin{aligned} \operatorname{corona}(G_2)\cup N(\operatorname{core}(G_2)) =& \operatorname{corona}(G_2)\cup N(\emptyset) \\ =& \{u_1,u_2,v_1,v_2\} \\ &\neq& V(G_2), \end{aligned}\] because the common vertex \(w\) is missing.
Finally, \(G_2\) is not König–Egerváry. Since \(|V(G_2)|=5\), every matching has size at most \(2\). The set \(\{u_1u_2,v_1v_2\}\) is a matching of size \(2\), so \(\mu(G_2)=2\). Hence \[\begin{aligned} \alpha(G_2)+\mu(G_2) =& 2+2 \\ =& 4 \\ <& 5 \\ =& |V(G_2)|. \end{aligned}\]
Therefore \(G_2\) is not a König–Egerváry graph.
Example 5.3 (Conditions (A2) and (A3) do not imply (A1)). Let \(G_3\) be the graph obtained from \(K_4\) by adding one pendant vertex. Let the vertices of the \(K_4\) be \(y,x_1,x_2,x_3\), and let \(p\) be the pendant vertex adjacent only to \(y\). Thus \[V(G_3)=\{p,y,x_1,x_2,x_3\},\] and \[E(G_3)=E\bigl(K_4[\{y,x_1,x_2,x_3\}]\bigr)\cup\{py\}.\]
The maximum independent sets of \(G_3\) are exactly \[\Omega(G_3)=\bigl\{\{p,x_1\},\{p,x_2\},\{p,x_3\}\bigr\}.\]
Therefore \[\alpha(G_3)=2, \qquad \operatorname{core}(G_3)=\{p\}, \qquad \operatorname{corona}(G_3)=\{p,x_1,x_2,x_3\}.\]
Since \[N(\operatorname{core}(G_3))=N(\{p\})=\{y\},\] we obtain \[\begin{aligned} \operatorname{corona}(G_3)\cup N(\operatorname{core}(G_3)) =& \{p,x_1,x_2,x_3\}\cup\{y\} \\ =& V(G_3). \end{aligned}\]
Thus (A2) holds.
Moreover, \(\operatorname{core}(G_3)\) is critical. Indeed, \[\begin{aligned} d(\operatorname{core}(G_3)) =& d(\{p\}) \\ =& |\{p\}|-|N(\{p\})| \\ =& 1-1 \\ =& 0. \end{aligned}\]
There is no independent set with positive difference: \(d(\emptyset)=0\); \(d(\{p\})=0\); every singleton contained in the \(K_4\) has negative difference; and every independent set of size \(2\) is of the form \(\{p,x_i\}\), whose neighborhood has size \(3\). Therefore \(d_I(G_3)=0\). Since \(d(G_3)=d_I(G_3)\) [25], we obtain \(d(G_3)=0\), and \(\operatorname{core}(G_3)\) is critical. Hence (A3) holds.
However, (A1) fails, because \[\begin{aligned} |\operatorname{core}(G_3)|+|\operatorname{corona}(G_3)| =& 1+4 \\ =& 5, \end{aligned}\] whereas \[2\alpha(G_3)=4.\]
Thus \[|\operatorname{core}(G_3)|+|\operatorname{corona}(G_3)|\neq 2\alpha(G_3).\]
Finally, \(G_3\) is not König–Egerváry. Since \(|V(G_3)|=5\), every matching has size at most \(2\). The set \(\{py,x_1x_2\}\) is a matching of size \(2\), so \(\mu(G_3)=2\). Therefore \[\begin{aligned} \alpha(G_3)+\mu(G_3) =& 2+2 \\ =& 4 \\ <& 5 \\ =& |V(G_3)|. \end{aligned}\]
Thus \(G_3\) is not a König–Egerváry graph.
The examples above show that the three assumptions in the core–corona characterization are genuinely needed. The equality in (A1) alone does not control criticality; the covering condition (A2) may fail even when the core is critical; and the criticality of the core together with the covering condition does not force the numerical identity in (A1). Hence the conjunction of all three conditions is essential for the sufficiency direction of the characterization.
The three conditions considered in this paper arise naturally in the study of König–Egerváry graphs, but each of them is only necessary when taken separately. Our result shows that their intersection contains no additional graphs: the graphs satisfying the core–corona identity, the covering condition, and the criticality of the core are precisely the König–Egerváry graphs.
In this sense, the theorem identifies the exact point at which the core–corona structure of maximum independent sets agrees with the critical difference structure. The examples in Section 5 show that this agreement is genuinely threefold: no pair of the three conditions is sufficient.
During the preparation of this work the authors used ChatGPT-3.5 in order to improve the grammar of several paragraphs of the text. After using this service, the authors reviewed and edited the content as needed and take full responsibility for the content of the publication.