Sterboul’s theorem characterizes non-Kőnig–Egerváry graphs by the presence, relative to a maximum matching, of a flower or a posy. In this paper we translate that obstruction into the language of perfect flowers and the core of the graph. We introduce core-defective perfect flowers: perfect flowers whose alternating path contains a vertex at odd distance from the blossom base that does not belong to the core. We prove first that every Kőnig–Egerváry graph is core-rigid: in every perfect flower, all odd-distance vertices of the attaching path lie in the core. Conversely, if \(G\) is connected and is not an odd cycle, then \(G\) is non-Kőnig–Egerváry if and only if \(G\) contains a core-defective perfect flower. Thus, among connected graphs different from an odd cycle, the Kőnig–Egerváry graphs are exactly the graphs with no core-defective perfect flower. In the matchable case the statement strengthens: if \(G\) has a perfect matching, then being non-Kőnig–Egerváry is equivalent to the existence of a core-defective perfect flower for some maximum matching, and also equivalent to the existence of one for every maximum matching. We include examples and counterexamples showing why odd cycles, disconnected graphs, and the universal quantifier over maximum matchings require separate treatment.
Let \(\alpha(G)\) denote the cardinality of a maximum independent set of a graph \(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)\le |V(G)|.\]
A graph \(G\) is called a Kőnig–Egerváry graph if equality holds, that is, \[\alpha(G)+\mu(G)=|V(G)|,\] see [4, 8, 17]. Kőnig–Egerváry graphs have been extensively studied from algorithmic, matching-theoretic, and independence-theoretic viewpoints [1, 3, 9, 12, 13]. Every bipartite graph is Kőnig–Egerváry, a fact going back to the classical theorem of Kőnig and Egerváry [7].
One of the most useful forbidden-configuration characterizations of this class is due to Sterboul [17]. It states that a graph is non-Kőnig–Egerváry if and only if, relative to every maximum matching, equivalently relative to some maximum matching, the graph contains a flower or a posy. The language originates in Edmonds’ blossom theory [6]; later work reformulated and extended this point of view through forbidden subgraphs and generalized Sterboul–Deming configurations [1, 10].
Perfect flowers were introduced by Pereyra in [15] in connection with the perfect-flower decomposition \[V(G)=PF(G)\cup PFF(G),\] and determinant and permanent factorizations for Kőnig–Egerváry graphs. More precisely, for every Kőnig–Egerváry graph \(G\), the perfect-flower part \(PF(G)\) and the perfect-flower-free part \(PFF(G)\) satisfy \[\det(G)=\det(G[PF(G)])\det(G[PFF(G)]),\] and the analogous identity for the permanent also holds [15]. The present work is complementary. Instead of asking how perfect flowers factor matrix invariants inside the Kőnig–Egerváry class, we ask how perfect flowers recognize the failure of the Kőnig–Egerváry property itself.
This distinction is important for the novelty of the paper. We do not reprove Sterboul’s flower–posy obstruction theorem, nor do we claim that perfect flowers replace that theorem independently. Rather, we use Sterboul’s obstructions as input and transform them into perfect-flower obstructions with an additional core condition. The new ingredients are the core-forcing lemma, the clean conversion of posies into core-defective perfect flowers, the switching treatment of ordinary flowers outside the odd-cycle exception, and the resulting distinction between existential and universal quantifiers over maximum matchings.
The answer is that the core is the missing ingredient. From [11], recall that \[\operatorname{core}(G)=\bigcap\{I:I\text{ is a maximum independent set of }G\}.\]
If \((C,P)\) is a perfect flower, then the path \(P\) starts at the base of an odd blossom and begins and ends with matching edges. Hence the vertices of \(P\) at odd distance from the base form a distinguished parity class. We call a perfect flower core-defective if at least one of these odd-distance vertices does not belong to \(\operatorname{core}(G)\).
The main result of the paper is the following connected characterization.
Theorem 1.1(Connected characterization).Let \(G\) be a connected graph. Then \(G\) is not a Kőnig–Egerváry graph if and only if either \(G\) is an odd cycle or \(G\) contains a core-defective perfect flower. Consequently, if \(G\) is connected and is not an odd cycle, then \(G\) is Kőnig–Egerváry if and only if it has no core-defective perfect flower.
Odd cycles are the only connected exception: they are non-Kőnig–Egerváry, but a maximum matching leaves one vertex of the cycle exposed and there is no non-trivial attaching path from the blossom. In the matchable case the characterization becomes stronger.
Theorem 1.2(Matchable strengthening).Let \(G\) be a graph with a perfect matching. Then the following statements are equivalent.
(i) \(G\) is not a Kőnig–Egerváry graph.
(ii) For some maximum matching \(M\) of \(G\), the graph \(G\) contains a core-defective \(M\)-perfect flower.
(iii) For every maximum matching \(M\) of \(G\), the graph \(G\) contains a core-defective \(M\)-perfect flower.
Let us make the dependence on Sterboul’s theorem explicit. The implication from a core-defective perfect flower to non-Kőnig–Egerváry is obtained directly from the core-forcing lemma, Theorem 3.1, and does not use Sterboul’s theorem. The converse implications do use Sterboul’s theorem as their starting point. In the matchable case, Sterboul’s theorem gives a posy for each maximum matching, and Lemmas 3.4 and 3.5 convert it into a core-defective perfect flower. In the connected non-matchable case, posies are handled in the same way, while ordinary flowers require the switching and exposed-blossom arguments of Lemmas 5.1–5.4. Thus the main characterizations should be read as core-theoretic transformations of Sterboul flower–posy obstructions, together with the new core-forcing direction, rather than as a wholly independent obstruction theorem.
The perfect-matching hypothesis is essential only for the universal quantifier over maximum matchings. Without it, ordinary flowers can occur, and some maximum matchings may have no perfect flower at all. We include a connected counterexample showing that the existential characterization cannot be upgraded to a universal one over all maximum matchings without the perfect-matching assumption.
The paper is organized as follows. Section 2 contains the terminology and the auxiliary definitions. Section 3 proves the core-forcing direction and the posy reduction. Section 4 proves the perfect-matching characterization. Section 5 proves the connected characterization without assuming a perfect matching. Section 6 gives the counterexample to the universal quantifier in the non-matchable case. Sections 7 and 8 contain examples and 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 [14] or Diestel [5]. 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\ne v\}\). We write \(uv\) for the edge \(\{u,v\}\). 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)\). If \(X\subseteq V(G)\), the subgraph induced by \(X\) is denoted by \(G[X]\) and is defined by \(V(G[X])=X\) and \(E(G[X])=\{uv\in E(G):u,v\in X\}\). 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 order of \(G\) is \(|G|=|V(G)|\).
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: ux\in E(G)\text{ for some }x\in X\}.\]
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 \(G\) is a set of pairwise non-adjacent edges. The matching number of \(G\), denoted by \(\mu(G)\), is the maximum cardinality of a matching in \(G\). A matching of cardinality \(\mu(G)\) is called a maximum matching. A matching \(M\) is perfect if every vertex of \(G\) is incident with an edge of \(M\). If \(M\) is a matching, a vertex is \(M\)-saturated if it is incident with an edge of \(M\), and \(M\)-unsaturated otherwise. An \(M\)-alternating path is a path whose edges alternate between belonging to \(M\) and not belonging to \(M\).
A set \(I\subseteq V(G)\) is independent if no two vertices of \(I\) are adjacent. The independence number of \(G\), denoted by \(\alpha(G)\), is the maximum cardinality of an independent set in \(G\). We write \(\Omega(G)\) for the family of maximum independent sets of \(G\). The core of \(G\) is \[\operatorname{core}(G)=\bigcap\{I:I\in\Omega(G)\}.\]
Thus \(\operatorname{core}(G)\) is an independent set. The core and related families of maximum independent sets have been studied extensively; see, for instance, [2, 11, 13].
Since every edge of a matching must meet the complement of any maximum independent set, one always has \[\alpha(G)+\mu(G)\le |V(G)|.\]
A graph \(G\) is a Kőnig–Egerváry graph if equality holds, that is, \[\alpha(G)+\mu(G)=|V(G)|.\]
Following Pulleyblank [16], a graph is called \(2\)-bicritical if \[|N(S)|>|S|,\] for every non-empty independent set \(S\) of \(G\).
We now recall the matching configurations used in the paper. The terminology of blossoms and flowers comes from Edmonds [6]; posies were introduced by Sterboul [17].
Definition 2.1(Blossoms, flowers and posies). Let \(M\) be a maximum matching of a graph \(G\).
(a) An \(M\)–blossom is an odd cycle of length \(2k+1\) containing exactly \(k\) edges of \(M\). The unique vertex of the cycle not saturated by the edges of \(M\) lying on the cycle is called the base of the blossom.
(b) An \(M\)–stem is an \(M\)-alternating path of even length, possibly zero, joining the base of an \(M\)-blossom to a vertex not saturated by \(M\) in \(G\), and meeting the blossom only in the base.
(c) An \(M\)–flower is an \(M\)-blossom together with an \(M\)-stem. The vertex not saturated by \(M\) in the stem is called the root of the flower.
(d) An \(M\)–posy consists of two \(M\)-blossoms joined by an \(M\)-alternating path whose first and last edges belong to \(M\), and whose endpoints are the bases of the two blossoms.
The terminology is meant to match the Sterboul–Edmonds convention used in the cited matching literature. The only conventions that will matter later are the following. Stems of ordinary flowers are allowed to have length zero; this is why an odd cycle itself may occur as an ordinary flower. By contrast, the attaching path in a perfect flower, defined below, is required to be non-trivial: length one is allowed, but length zero is not. We also do not impose a clean-disjointness condition on the joining path of a posy at the level of the definition. If one uses a convention in which posies are already clean, Lemma 3.4 below shows that the two formulations are equivalent for the arguments of this paper.
Theorem 2.2 (Sterboul [17]). For a graph \(G\), the following statements are equivalent.
(i) \(G\) is not a Kőnig–Egerváry graph.
(ii) For every maximum matching \(M\) of \(G\), there exists an \(M\)-flower or an \(M\)-posy in \(G\).
(iii) For some maximum matching \(M\) of \(G\), there exists an \(M\)-flower or an \(M\)-posy in \(G\).
Definition 2.3(Perfect flower [15]).Let \(M\) be a maximum matching of \(G\). An \(M\)–perfect flower is a pair \((C,P)\) such that:
(a) \(C\) is an odd cycle of length \(2k+1\) containing exactly \(k\) edges of \(M\);
(b) \(P=p_0,p_1,\ldots,p_t\) is a non-trivial \(M\)-alternating path whose first and last edges belong to \(M\);
(c) \(V(C)\cap V(P)=\{p_0\}\).
The vertex \(p_0\) is called the joint of the perfect flower. Since \(p_0p_1\in M\), the joint is the base of the \(M\)-blossom \(C\). Paths of length one are allowed in the definition; paths of length zero are not allowed.
The condition that the first and last edges of \(P\) belong to \(M\) implies that \(t\) is odd. Thus the vertices of \(P\) at odd distance from the joint are precisely \(p_1,p_3,\ldots,p_t\).
Definition 2.4(Odd side and core-defect).Let \((C,P)\) be an \(M\)-perfect flower with \(P=p_0,p_1,\ldots,p_t\). Define \[\operatorname{Odd}(C,P)=\{p_i:i\text{ is odd}\}.\]
Thus \(\operatorname{Odd}(C,P)\) is the set of vertices of \(P\) at odd distance from the joint \(p_0\). The perfect flower \((C,P)\) is core-defective if \[\operatorname{Odd}(C,P)\nsubseteq \operatorname{core}(G).\]
Equivalently, there exists \(z\in V(P)\) such that \(\operatorname{dist}_P(p_0,z)\) is odd and \(z\notin\operatorname{core}(G)\). When no matching is specified, saying that \(G\) contains a core-defective perfect flower means that this happens for some maximum matching of \(G\).
Lemma 2.5. Let \(G\) be a Kőnig–Egerváry graph, let \(M\) be a maximum matching of \(G\), and let \(I\) be a maximum independent set of \(G\). Then:
(a) \(I\) contains exactly one endpoint of every edge of \(M\);
(b) \(I\) contains every vertex unsaturated by \(M\).
Proof. Let \(U\) be the set of vertices unsaturated by \(M\). Since \(I\) is independent, it contains at most one endpoint of each edge of \(M\), and at most all vertices of \(U\). Hence \[|I|\le |M|+|U|=\mu(G)+|V(G)|-2\mu(G)=|V(G)|-\mu(G).\]
Because \(G\) is Kőnig–Egerváry, \(|V(G)|-\mu(G)=\alpha(G)\). Since \(I\) is maximum, \(|I|=\alpha(G)\), so equality holds throughout. Therefore \(I\) contains exactly one endpoint of each edge of \(M\) and contains every vertex unsaturated by \(M\). ◻
We first prove the one-way implication that holds for all graphs, with no perfect-matching assumption. It is the key reason for introducing the core in the definition of a core-defective perfect flower.
Theorem 3.1(Core-forcing lemma).Let \(G\) be a Kőnig–Egerváry graph, let \(M\) be a maximum matching of \(G\), and let \((C,P)\) be an \(M\)-perfect flower. If \(P=p_0,p_1,\ldots,p_t\) and \(V(C)\cap V(P)=\{p_0\}\), then \[p_1,p_3,\ldots,p_t\in \operatorname{core}(G).\]
Equivalently, \[\operatorname{Odd}(C,P)\subseteq \operatorname{core}(G).\]
Proof. Let \(I\) be an arbitrary maximum independent set of \(G\). By Lemma 2.5, \(I\) contains exactly one endpoint of every edge of \(M\).
Write the cycle \(C\) as \[C=c_0,c_1,\ldots,c_{2r},c_0,\] where \(c_0=p_0\). Since the first edge \(p_0p_1\) of \(P\) belongs to \(M\), the vertex \(p_0\) cannot be incident with an edge of \(M\) inside \(C\). Thus \(p_0=c_0\) is the base of the \(M\)-blossom \(C\). We may orient \(C\) so that \[c_1c_2,\ c_3c_4,\ \ldots,\ c_{2r-1}c_{2r},\] are precisely the edges of \(M\) lying on \(C\).
We claim first that \(p_0\notin I\). Suppose, to the contrary, that \(p_0=c_0\in I\). Since \(c_0c_1\in E(G)\), we have \(c_1\notin I\). As \(c_1c_2\in M\) and \(I\) contains exactly one endpoint of this matching edge, it follows that \(c_2\in I\). Then \(c_2c_3\in E(G)\) gives \(c_3\notin I\), and the matching edge \(c_3c_4\) forces \(c_4\in I\). Continuing around the cycle yields \(c_{2r}\in I\). But \(c_{2r}\) is adjacent to \(c_0=p_0\), contradicting the independence of \(I\). Therefore \(p_0\notin I\).
Now consider the path \[P=p_0,p_1,\ldots,p_t.\]
Because \(P\) is alternating and its first and last edges belong to \(M\), we have \[p_{i-1}p_i\in M \quad\Longleftrightarrow\quad i\text{ is odd}.\]
Since \(p_0\notin I\) and \(p_0p_1\in M\), Lemma 2.5 gives \(p_1\in I\). Then \(p_1p_2\in E(G)\) gives \(p_2\notin I\), and the matching edge \(p_2p_3\in M\) gives \(p_3\in I\). Inductively, \[p_1,p_3,\ldots,p_t\in I.\]
The maximum independent set \(I\) was arbitrary. Hence all these vertices belong to the intersection of all maximum independent sets, namely to \(\operatorname{core}(G)\). ◻
Corollary 3.2. If \(G\) has a maximum matching \(M\) for which there exists a core-defective \(M\)-perfect flower, then \(G\) is not a Kőnig–Egerváry graph.
Proof. This is the contrapositive of Theorem 3.1. ◻
Remark 3.3. Theorem 3.1 explains the role of the core. A perfect flower by itself is not an obstruction to the Kőnig–Egerváry property. In a Kőnig–Egerváry graph, perfect flowers may exist, but their odd path vertices are forced into \(\operatorname{core}(G)\). The obstruction is not the flower; it is the failure of this core-forcing phenomenon.
The definition of an \(M\)-posy does not require the joining path to avoid the two blossoms. The next lemma shows that this causes no difficulty: every posy has a clean representative.
Lemma 3.4(Clean posy reduction).Let \(M\) be a maximum matching of a graph \(G\). If \(G\) contains an \(M\)-posy, then \(G\) contains an \(M\)-posy represented by two \(M\)-blossoms \(C_1,C_2\), with bases \(a,b\), and an \(M\)-alternating path \[Q=q_0,q_1,\ldots,q_\ell, \qquad q_0=a, \qquad q_\ell=b,\] whose first and last edges belong to \(M\), and such that \[V(Q)\cap V(C_1)=\{a\}, \qquad V(Q)\cap V(C_2)=\{b\}.\]
Proof. Choose, among all triples witnessing an \(M\)-posy, one for which the length of the joining path \(Q\) is minimum. We prove that this representative is clean.
Suppose first that some internal vertex of \(Q\) lies in \(C_1\). Let \(i>0\) be the smallest index such that \(q_i\in V(C_1)\). Then \(q_i\ne a\), and the prefix \(q_0,q_1,\ldots,q_i\) meets \(C_1\) only at its endpoints. Since \(C_1\) is an \(M\)-blossom with base \(a\), the vertex \(q_i\) is saturated by exactly one edge of \(M\) lying on \(C_1\). Hence the edge \(q_{i-1}q_i\) cannot belong to \(M\), for otherwise \(q_i\) would be incident with two distinct edges of the matching \(M\). Because \(Q\) starts with an edge of \(M\), this means that \(i\) is even.
Among the two \(a\)–\(q_i\) arcs of \(C_1\), choose the arc \(A\) whose last edge at \(q_i\) is not in \(M\). The union of \(A\) with the prefix \(q_0,q_1,\ldots,q_i\) is an odd cycle \(D\) with exactly \((|D|-1)/2\) edges of \(M\), and its base is \(q_i\). Thus \(D\) is an \(M\)-blossom. Since \(i\) is even, the suffix \[q_i,q_{i+1},\ldots,q_\ell,\] starts with an edge of \(M\) and still ends with an edge of \(M\). Therefore \(D\), this suffix of \(Q\), and \(C_2\) form an \(M\)-posy with a shorter joining path, a contradiction. Hence no internal vertex of \(Q\) lies in \(C_1\).
Applying the same argument to the reversed path and the blossom \(C_2\), no internal vertex of \(Q\) lies in \(C_2\).
It remains only to rule out the possibility that the other endpoint lies in the wrong blossom. If \(b\in V(C_1)\), then \(b\ne a\) is saturated by an edge of \(M\) lying on \(C_1\). But \(b\) is also incident with the last edge \(q_{\ell-1}b\) of \(Q\), which belongs to \(M\). This is a distinct matching edge: if \(\ell>1\), then \(q_{\ell-1}\) is an internal vertex of \(Q\) and hence is not in \(C_1\); if \(\ell=1\), then \(q_{\ell-1}=a\), and the base \(a\) is not incident with any edge of \(M\) lying on \(C_1\). This contradicts that \(M\) is a matching. Thus \(b\notin V(C_1)\). Similarly, \(a\notin V(C_2)\). The chosen representative therefore satisfies the desired equalities. ◻
Lemma 3.5(Posies give core-defective perfect flowers).Let \(M\) be a maximum matching of a graph \(G\). If \(G\) contains an \(M\)-posy, then \(G\) contains a core-defective \(M\)-perfect flower.
Proof. By Lemma 3.4, choose a clean representative of the posy, with two \(M\)-blossoms \(C_1,C_2\), bases \(a,b\), and joining path \[Q=q_0,q_1,\ldots,q_\ell, \qquad q_0=a, \qquad q_\ell=b,\] such that \(V(Q)\cap V(C_1)=\{a\}\) and \(V(Q)\cap V(C_2)=\{b\}\). The first and last edges of \(Q\) belong to \(M\), so \(\ell\) is odd.
The pair \((C_1,Q)\) is an \(M\)-perfect flower with joint \(a\). If \(b\notin\operatorname{core}(G)\), then \(b\) is an odd-distance vertex on \(Q\), and this perfect flower is core-defective.
Assume now that \(b\in\operatorname{core}(G)\). Since \(\operatorname{core}(G)\) is independent and \(q_{\ell-1}b\in E(G)\), we have \[q_{\ell-1}\notin\operatorname{core}(G).\]
Using the second blossom and the reversed path, the pair \[\bigl(C_2,\ b,q_{\ell-1},q_{\ell-2},\ldots,q_0\bigr),\] is an \(M\)-perfect flower. Its vertex \(q_{\ell-1}\) is at distance one from the joint \(b\), and it is not in the core. Hence this perfect flower is core-defective. ◻
We now prove the main result. The proof uses Sterboul’s theorem and the fact that, in a graph with a perfect matching, every maximum matching is perfect.
Theorem 4.1(Perfect-flower characterization in the matchable case).Let \(G\) be a graph with a perfect matching. Then the following statements are equivalent.
(i) \(G\) is not a Kőnig–Egerváry graph.
(ii) For some maximum matching \(M\) of \(G\), the graph \(G\) contains a core-defective \(M\)-perfect flower.
(iii) For every maximum matching \(M\) of \(G\), the graph \(G\) contains a core-defective \(M\)-perfect flower.
Proof. We prove \((i)\Rightarrow(iii)\Rightarrow(ii)\Rightarrow(i)\).
Assume first that \(G\) is not Kőnig–Egerváry, and let \(M\) be an arbitrary maximum matching of \(G\). Since \(G\) has a perfect matching, \(\mu(G)=|V(G)|/2\), and therefore every maximum matching of \(G\) is perfect. In particular, \(M\) is perfect.
By Sterboul’s theorem, with respect to this maximum matching \(M\), the graph \(G\) contains an \(M\)-flower or an \(M\)-posy. An ordinary \(M\)-flower has a root not saturated by \(M\). Since \(M\) is perfect, no such root exists. Hence \(G\) contains an \(M\)-posy.
By Lemma 3.5, this \(M\)-posy yields a core-defective \(M\)-perfect flower. Since \(M\) was an arbitrary maximum matching, this proves \((i)\Rightarrow(iii)\).
The implication \((iii)\Rightarrow(ii)\) is immediate.
Finally, \((ii)\Rightarrow(i)\) is exactly Corollary 3.2. The equivalence follows. ◻
Corollary 4.2(Konig–Egervary form).Let \(G\) be a graph with a perfect matching. Then the following statements are equivalent.
(i) \(G\) is a Kőnig–Egerváry graph.
(ii) For every maximum matching \(M\) of \(G\) and every \(M\)-perfect flower \((C,P)\), one has \(\operatorname{Odd}(C,P)\subseteq \operatorname{core}(G)\).
(iii) There exists a maximum matching \(M\) of \(G\) such that no \(M\)-perfect flower is core-defective.
Proof. The equivalence of (i) and (ii) follows from Theorem 3.1 and Theorem 4.1. The equivalence with (iii) is the negation of the implication in Theorem 4.1 saying that, if \(G\) is non-Kőnig–Egerváry, then every maximum matching admits a core-defective perfect flower. ◻
We now remove the perfect-matching hypothesis from the existential part of Theorem 4.1. The price is one unavoidable exception: an odd cycle is non-Kőnig–Egerváry, but it has no perfect flower. The proof uses Lemma 3.5 for posies. For ordinary flowers we separate the argument into three elementary lemmas: switching an odd alternating exit, treating an exposed blossom with vertices outside it, and treating the remaining Hamiltonian odd case where the blossom spans the whole graph but the graph has a chord.
Lemma 5.1(Switching an alternating exit).Let \(M\) be a maximum matching of \(G\), and let \(C\) be an \(M\)-blossom whose base \(x\) is not saturated by \(M\) in \(G\). Suppose there is an \(M\)-alternating path \[R=x=r_0,r_1,\ldots,r_{2q+1}=z,\] such that \(R\) meets \(C\) only in \(x\), its first and last edges do not belong to \(M\), and \[z\notin\operatorname{core}(G).\]
Then \(G\) contains a core-defective perfect flower.
Proof. Since \(M\) is maximum, the endpoint \(z\) is saturated by \(M\); otherwise \(R\) would be an \(M\)-augmenting path starting at the unsaturated vertex \(x\) and ending at the unsaturated vertex \(z\). Let \(zz'\) be the edge of \(M\) incident with \(z\).
We first verify that \(z'\) is outside \(R\). Because the first edge of \(R\) is not in \(M\), the alternating pattern is \[r_{i-1}r_i\in M \quad\Longleftrightarrow\quad i\text{ is even}.\]
Thus every internal vertex \(r_i\), \(1\le i\le 2q\), is already saturated by an \(M\)-edge lying on \(R\): if \(i\) is odd, this edge is \(r_ir_{i+1}\), and if \(i\) is even, it is \(r_{i-1}r_i\). The initial vertex \(x=r_0\) is not saturated by \(M\) in \(G\), and the last edge \(r_{2q}z\) is not in \(M\). Hence the \(M\)-mate \(z'\) of \(z\) cannot be any vertex of \(R\). Moreover, \(z'\) is not on \(C\): the path \(R\) meets \(C\) only in \(x\), and every vertex of \(C\) other than the base is already matched by an edge of \(M\) lying on \(C\), while \(x\) is \(M\)-unsaturated.
Define \[M'=(M\setminus (E(R)\cup\{zz'\}))\cup (E(R)\setminus M).\]
This is a matching. Indeed, each internal vertex of \(R\) loses its unique \(M\)-edge on \(R\) and gains the other incident edge of \(R\); the vertex \(x\) gains the edge \(xr_1\); the vertex \(z\) loses \(zz'\) and gains \(r_{2q}z\); the vertex \(z'\) loses \(zz'\) and gains no edge; and all vertices outside \(V(R)\cup\{z'\}\) keep their previous incident matching edge, if any. The verification that \(z'\notin V(R)\) is what prevents a conflict at the last step.
The path \(R\) contains \(q\) edges of \(M\) and \(q+1\) edges not in \(M\). Therefore the above operation removes \(q+1\) edges, namely the \(q\) matching edges on \(R\) together with \(zz'\), and adds \(q+1\) edges. Hence \(|M'|=|M|\), so \(M'\) is again a maximum matching.
No edge of \(C\) is changed. Consequently \(C\) remains an odd cycle with exactly \((|C|-1)/2\) edges of \(M'\), and \(x\) remains the unique vertex of \(C\) not saturated by matching edges lying on \(C\). Along \(R\), the membership of each edge has been toggled: the first and last edges of \(R\) now belong to \(M'\), and the edges still alternate with respect to \(M'\). Since \(R\) meets \(C\) only in \(x\), the pair \((C,R)\) is an \(M'\)-perfect flower. Its endpoint \(z\) is at odd distance from the joint \(x\) and satisfies \(z\notin\operatorname{core}(G)\); hence this perfect flower is core-defective. ◻
Lemma 5.2(Exposed blossoms with an outside vertex). Let \(G\) be connected, let \(N\) be a maximum matching of \(G\), and let \(C\) be an \(N\)-blossom whose base is not saturated by \(N\) in \(G\). If \[V(G)\setminus V(C)\ne\varnothing,\] then \(G\) contains a core-defective perfect flower.
Proof. For each vertex \(u\in V(C)\), let \(N_u\) be the matching obtained from \(N\) by rotating the matching edges on the odd cycle \(C\) so that \(u\) is the unique vertex of \(C\) not saturated by matching edges lying on \(C\), while \(N\) is left unchanged outside \(C\). Since the rotation replaces \((|C|-1)/2\) edges by the same number of edges, \(N_u\) is again a maximum matching. Moreover, no edge of \(N_u\) joins \(C\) to \(V(G)\setminus V(C)\): the vertices of \(C\) different from the base are matched inside \(C\), and the base is unsaturated in \(G\) before the rotation and remains the only vertex of \(C\) not matched inside \(C\) after the rotation.
For such a vertex \(u\), an odd \(N_u\)-exit from \(C\) means an \(N_u\)-alternating path \[P=u=w_0,w_1,\ldots,w_{2q+1}=z,\] contained in \(G-(V(C)\setminus\{u\})\), with endpoint \(z\notin V(C)\), whose first and last edges do not belong to \(N_u\). Thus every exit is already a path and meets \(C\) only in its initial vertex \(u\). Let \(O_u\) be the set of endpoints of all odd \(N_u\)-exits from \(C\), and put \[O=\bigcup_{u\in V(C)}O_u.\]
Claim 1. \(O\) is non-empty. Connectedness is used here. Since \(G\) is connected and \(V(G)\setminus V(C)\ne\varnothing\), some vertex \(u\in V(C)\) has a neighbour \(z\notin V(C)\). The one-edge path \(u,z\) is an odd \(N_u\)-exit from \(C\), because no edge of \(N_u\) joins \(C\) to the outside. Hence \(z\in O\).
If \(O\) contains a vertex \(z\notin\operatorname{core}(G)\), then by definition there is an odd exit path from some \(u\in V(C)\) to \(z\). Lemma 5.1, applied to the matching \(N_u\), gives a core-defective perfect flower. We may therefore assume, for a contradiction, that \[O\subseteq\operatorname{core}(G).\]
Claim 2. every vertex of \(O\) is saturated by \(N\). This is where maximality of the matching is used. Let \(z\in O_u\), and let \(P\) be an odd \(N_u\)-exit from \(u\) to \(z\). If \(z\) were not saturated by \(N_u\), then \(P\) would be an \(N_u\)-augmenting path: it starts at the \(N_u\)-unsaturated vertex \(u\), ends at the \(N_u\)-unsaturated vertex \(z\), and its first and last edges are not in \(N_u\). This contradicts the maximality of \(N_u\). Since \(N_u\) and \(N\) coincide outside \(C\), the vertex \(z\) is also saturated by \(N\).
Let \(E_O\) denote the set of \(N\)-mates of vertices of \(O\): \[E_O=\{e\in V(G): eo\in N\text{ for some }o\in O\}.\]
By Claim 2, the matching \(N\) gives a bijection between \(O\) and \(E_O\), and hence \[|E_O|=|O|.\]
Also \(E_O\subseteq V(G)\setminus V(C)\), because no edge of \(N\) joins \(C\) to the outside.
Claim 3. every outside neighbour of \(C\) lies in \(O\), and no vertex of \(E_O\) is adjacent to \(C\). For the first assertion, if \(cw\in E(G)\) with \(c\in V(C)\) and \(w\notin V(C)\), then the one-edge path \(c,w\) is an odd \(N_c\)-exit, so \(w\in O\). This uses the definition of the rotated matching \(N_c\) and the fact that no matching edge leaves \(C\).
For the second assertion, suppose that some \(e\in E_O\) is adjacent to a vertex \(c\in V(C)\). By the first assertion, \(e\in O\). Let \(o\in O\) be the \(N\)-mate of \(e\). Under the standing contradiction hypothesis \(O\subseteq\operatorname{core}(G)\), both \(e\) and \(o\) would belong to the independent set \(\operatorname{core}(G)\), while \(eo\in E(G)\). This is impossible. Thus no vertex of \(E_O\) has a neighbour in \(C\).
Claim 4. \(E_O\cap O=\varnothing\) and \(N_G(E_O)\subseteq O\). The disjointness uses the assumption \(O\subseteq\operatorname{core}(G)\). Each vertex \(e\in E_O\) is adjacent to its mate \(o\in O\subseteq\operatorname{core}(G)\), so \(e\notin\operatorname{core}(G)\) because the core is independent. Hence \(e\notin O\), and \(E_O\cap O=\varnothing\).
Now let \(e\in E_O\), let \(o\in O\) be its \(N\)-mate, and let \(w\) be a neighbour of \(e\). If \(w=o\), then \(w\in O\). Assume \(w\ne o\). Then \(ew\notin N\). By Claim 3, \(w\notin V(C)\). Choose an odd \(N_u\)-exit \[P=u=w_0,w_1,\ldots,w_{2q+1}=o,\] from \(C\) to \(o\). The vertex \(e\) does not lie on \(P\): if it were an internal vertex of \(P\), it would be incident with an \(N_u\)-matching edge of \(P\), distinct from its matching edge \(eo\); and it is not the initial vertex because \(e\notin V(C)\), nor the final vertex because \(e\ne o\).
If \(w\) is not a vertex of \(P\), then appending the matching edge \(oe\) and the non-matching edge \(ew\) gives an odd \(N_u\)-alternating path from \(C\) to \(w\), so \(w\in O\). If \(w=w_j\) for some \(j\) on \(P\) and \(j\) is odd, then the prefix \(u=w_0,\ldots,w_j=w\) is an odd exit, so again \(w\in O\). If \(j\) is even, then the prefix \(u=w_0,\ldots,w_j=w\) followed by the non-matching edge \(we\) is an odd \(N_u\)-exit from \(C\) to \(e\), because \(e\) is not on \(P\); this would imply \(e\in O\), contradicting \(E_O\cap O=\varnothing\). Therefore the even case cannot occur, and every neighbour \(w\) of \(e\) lies in \(O\). Hence \(N_G(E_O)\subseteq O\).
It follows at once that \(E_O\) is independent: if two vertices of \(E_O\) were adjacent, then one of them would lie in \(N_G(E_O)\subseteq O\), contradicting \(E_O\cap O=\varnothing\).
Claim 5. the maximum-independent-set exchange gives a contradiction. Let \(I\) be a maximum independent set of \(G\). Since \(O\subseteq\operatorname{core}(G)\), we have \(O\subseteq I\). Let \(A\) be a maximum independent set of the induced subgraph \(G[V(C)]\), and define \[I'=(I\setminus (O\cup V(C)))\cup E_O\cup A.\]
The set \(I'\) is independent. The set \(A\) is independent in \(G[V(C)]\); the set \(E_O\) is independent by Claim 4; there are no edges between \(E_O\) and \(V(C)\) by Claim 3; there are no edges from \(E_O\) to \(I\setminus(O\cup V(C))\) by Claim 4; and there are no edges from \(A\subseteq V(C)\) to \(I\setminus(O\cup V(C))\) because every outside neighbour of \(C\) lies in \(O\) by Claim 3.
Moreover, \(E_O\cap I=\varnothing\), because every vertex of \(E_O\) is adjacent to a vertex of \(O\subseteq I\). Therefore \[|I'| = |I|-|O|-|I\cap V(C)|+|E_O|+|A| = |I|-|I\cap V(C)|+|A| \ge |I|,\] where the equality uses \(|E_O|=|O|\) and the inequality uses the maximality of \(A\) in \(G[V(C)]\). Thus \(I'\) is also a maximum independent set of \(G\). But \(I'\) is disjoint from the non-empty set \(O\), while \(O\subseteq\operatorname{core}(G)\) must be contained in every maximum independent set. This contradiction proves that some odd exit ends at a vertex outside the core, and Lemma 5.1 gives a core-defective perfect flower. ◻
Lemma 5.3(The spanning chorded odd case).Let \(G\) be a graph whose vertex set is the vertex set of an odd cycle \(C\). If \(G\) is not equal to the cycle \(C\) as a graph, then \(G\) contains a core-defective perfect flower.
Proof. Since \(V(G)=V(C)\) and \(G\ne C\), the graph \(G\) has a chord of \(C\). Let this chord be \(ab\). The chord \(ab\) splits the odd cycle \(C\) into two \(a\)–\(b\) arcs. Exactly one of these arcs has even length. Denote the even arc by \[A:a=a_0,a_1,\ldots,a_{2s}=b, \qquad s\ge 1,\] and denote the other arc by \[B:a=b_0,b_1,\ldots,b_{2t},b_{2t+1}=b.\]
The length of \(B\) is odd; because \(ab\) is a chord, \(B\) has length at least three, and so \(t\ge 1\). The cycle \[D=A\cup\{ab\},\] is odd.
First choose the matching \[M_a= \{a_{2i-1}a_{2i}:1\le i\le s\} \cup\{b_0b_1\} \cup\{b_{2j}b_{2j+1}:1\le j\le t-1\}.\]
When \(t=1\), the last set is empty. This matching has \(s+t=(|G|-1)/2\) edges, and is therefore maximum. In the cycle \(D\), the matching \(M_a\) covers all vertices except \(a\), so \(D\) is an \(M_a\)-blossom based at \(a\). The path \[P_a=a,b_1,b_2,\ldots,b_{2t-1},\] is \(M_a\)-alternating, its first and last edges belong to \(M_a\), and it meets \(D\) only in \(a\). Hence \((D,P_a)\) is an \(M_a\)-perfect flower. Its odd side is \[\operatorname{Odd}(D,P_a)=\{b_1,b_3,\ldots,b_{2t-1}\}.\]
Similarly, choose the matching \[M_b= \{a_{2i}a_{2i+1}:0\le i\le s-1\} \cup\{b_{2t+1}b_{2t}\} \cup\{b_{2j+1}b_{2j}:1\le j\le t-1\}.\]
Again, if \(t=1\), the last set is empty. Again \(|M_b|=(|G|-1)/2\), so \(M_b\) is maximum. The cycle \(D\) is now an \(M_b\)-blossom based at \(b\), and \[P_b=b,b_{2t},b_{2t-1},\ldots,b_2,\] is an \(M_b\)-alternating path whose first and last edges belong to \(M_b\) and which meets \(D\) only in \(b\). Thus \((D,P_b)\) is an \(M_b\)-perfect flower, with \[\operatorname{Odd}(D,P_b)=\{b_{2t},b_{2t-2},\ldots,b_2\}.\]
The two odd sides just displayed cover all internal vertices of the arc \(B\): \[\operatorname{Odd}(D,P_a)\cup\operatorname{Odd}(D,P_b)=\{b_1,b_2,\ldots,b_{2t}\}.\]
These internal vertices cannot all belong to \(\operatorname{core}(G)\), because \(b_1b_2\in E(G)\) and the core is independent. Hence at least one of the two perfect flowers \((D,P_a)\) and \((D,P_b)\) has an odd-side vertex outside \(\operatorname{core}(G)\). That perfect flower is core-defective. ◻
Lemma 5.4(Ordinary flowers force defective perfect flowers).Let \(G\) be connected, let \(M\) be a maximum matching of \(G\), and suppose that \(G\) contains an \(M\)-flower with blossom \(C\). If \(G\) is not the cycle \(C\), then \(G\) contains a core-defective perfect flower.
Proof. Let \(x\) be the base of the blossom \(C\). Write the stem as \[S=s_0,s_1,\ldots,s_{2r}, \qquad s_0=x,\] where \(s_{2r}\) is not saturated by \(M\). In an \(M\)-flower the stem starts with an edge of \(M\) whenever \(r\ge 1\), and its edges alternate as \[s_{2i}s_{2i+1}\in M, \qquad s_{2i-1}s_{2i}\notin M.\]
Assume first that \(r\ge 1\). Then the stem has vertices outside the blossom. The prefix \[P=s_0,s_1,\ldots,s_{2r-1},\] is an \(M\)-alternating path whose first and last edges belong to \(M\), and it meets \(C\) only in \(x\). Hence \((C,P)\) is an \(M\)-perfect flower. If one of the vertices \[s_1,s_3,\ldots,s_{2r-1},\] does not belong to \(\operatorname{core}(G)\), then a shortest prefix ending at such a vertex gives a core-defective perfect flower.
We may therefore assume that all these odd stem vertices belong to \(\operatorname{core}(G)\). Switch the matching along the whole stem: \[N=M\triangle E(S).\]
The stem has the same number of matching and non-matching edges, so \(N\) is again a maximum matching. With respect to \(N\), the cycle \(C\) is still a blossom, but its base \(x\) is now not saturated by \(N\) in \(G\). Since \(r\ge 1\), the graph has vertices outside \(C\). Lemma 5.2 therefore gives a core-defective perfect flower.
It remains to consider \(r=0\). In this case the base of \(C\) is already not saturated by \(M\) in \(G\). If \(V(G)\setminus V(C)\ne\varnothing\), Lemma 5.2 applies directly. If \(V(G)=V(C)\), then the assumption \(G\ne C\) means that \(G\) has a chord of the odd cycle \(C\), and Lemma 5.3 gives a core-defective perfect flower. This proves the lemma. ◻
Theorem 5.5 (Connected perfect-flowers characterization).Let \(G\) be a connected graph. Then the following statements are equivalent:
(i) \(G\) is not a Kőnig–Egerváry graph.
(ii) Either \(G\) is an odd cycle, or \(G\) contains a core-defective perfect flower.
Consequently, if \(G\) is connected and is not an odd cycle, then \[G\text{ is K\H{o}nig–Egerv\'ary} \quad\Longleftrightarrow\quad G\text{ has no core-defective perfect flower.}\]
Proof. Assume first that \(G\) is not Kőnig–Egerváry. By Sterboul’s theorem, for some maximum matching \(M\) of \(G\), there exists an \(M\)-flower or an \(M\)-posy.
If there is an \(M\)-posy, Lemma 3.5 gives a core-defective perfect flower.
Suppose instead that there is an \(M\)-flower with blossom \(C\). If \(G=C\), then \(G\) is an odd cycle. If \(G\ne C\), Lemma 5.4 gives a core-defective perfect flower.
Thus every connected non-Kőnig–Egerváry graph is either an odd cycle or contains a core-defective perfect flower.
Conversely, every odd cycle is non-Kőnig–Egerváry, because \[\alpha(C_{2r+1})=r, \qquad \mu(C_{2r+1})=r, \qquad |C_{2r+1}|=2r+1.\]
Also, if \(G\) contains a core-defective perfect flower, then \(G\) is non-Kőnig–Egerváry by Corollary 3.2. This proves the equivalence. ◻
Corollary 5.6(Component-wise form).Let \(G\) be an arbitrary graph with connected components \(G_1,\ldots,G_s\). Then \(G\) is non-Kőnig–Egerváry if and only if at least one component \(G_i\) is either an odd cycle or contains a core-defective perfect flower. Equivalently, \(G\) is Kőnig–Egerváry if and only if every component is Kőnig–Egerváry, and Theorem 5.5 applies component by component.
Proof. The parameters \(\alpha\), \(\mu\), and \(|V|\) are additive over connected components. Hence \(G\) is Kőnig–Egerváry exactly when every component is Kőnig–Egerváry. If a component is an odd cycle, then that component, and therefore \(G\), is non-Kőnig–Egerváry. If a component contains a core-defective perfect flower, then the same perfect flower is also present in \(G\) after extending the relevant maximum matching to the remaining components, and Corollary 3.2 applies.
Conversely, if \(G\) is non-Kőnig–Egerváry, some component \(G_i\) is non-Kőnig–Egerváry. By Theorem 5.5, the connected graph \(G_i\) is either an odd cycle or contains a core-defective perfect flower. Finally, \(\operatorname{core}(G)=\bigcup_i\operatorname{core}(G_i)\), because maximum independent sets of \(G\) are precisely unions of maximum independent sets of its components; hence core-defectiveness in a component is the same as core-defectiveness in \(G\). ◻
Corollary 5.7. Let \(G\) be a connected graph which is not a cycle. Then \(G\) is non-Kőnig–Egerváry if and only if \(G\) contains a core-defective perfect flower.
Proof. An even cycle is Kőnig–Egerváry, and an odd cycle is the exceptional case in Theorem 5.5. Thus, if \(G\) is connected and is not a cycle, Theorem 5.5 gives the desired equivalence. ◻
Remark 5.8. Theorem 5.5 strengthens the purely existential statement that odd cycles are the only connected obstruction to the existence of perfect flowers. The stronger point is that, outside the odd cycle, the perfect flower can always be chosen to be core-defective.
Theorem 4.1 has the same “some maximum matching/every maximum matching” form as Sterboul’s theorem, but this is a consequence of the perfect-matching hypothesis. The connected characterization in Theorem 5.5 is necessarily existential.
Proposition 6.1(No universal quantifier without a perfect matching).There exists a connected graph \(G\) which is not a cycle and is not a Kőnig–Egerváry graph such that:
(i) for some maximum matching \(M\) of \(G\), there exists a core-defective \(M\)-perfect flower;
(ii) for another maximum matching \(N\) of \(G\), there is no \(N\)-perfect flower at all.
Consequently, in Theorem 5.5 the phrase “for some maximum matching” cannot be replaced by “for every maximum matching”.
Proof. Let \(G\) be the graph obtained from a triangle \(abc\) by attaching a path \(c-d-e\) at the vertex \(c\); see Figure 4. Thus \[V(G)=\{a,b,c,d,e\}, \qquad E(G)=\{ab,bc,ca,cd,de\}.\]
Then \(\mu(G)=2\), for instance by the matchings \(\{ab,cd\}\) and \(\{ab,de\}\). Also \(\alpha(G)=2\): one may choose one vertex from the triangle and one suitable vertex from the path, but no independent set has size three. Therefore \[\alpha(G)+\mu(G)=2+2=4<5=|V(G)|,\] so \(G\) is not Kőnig–Egerváry.
First take \[M=\{ab,cd\}.\]
The triangle \(abc\) is an \(M\)-blossom with base \(c\), and the path \(P=c,d\) is non-trivial, \(M\)-alternating, and its unique edge belongs to \(M\). Hence \((abc,c d)\) is an \(M\)-perfect flower. The maximum independent sets of \(G\) are \[\{a,d\},\ \{b,d\},\ \{a,e\},\ \{b,e\},\ \{c,e\},\] so \(\operatorname{core}(G)=\varnothing\). Thus the vertex \(d\), which is at distance one from the joint \(c\), is not in the core. The perfect flower is core-defective.
Now take \[N=\{ab,de\}.\]
The only odd cycle of \(G\) is the triangle \(abc\). With respect to \(N\), this triangle is an \(N\)-blossom whose base is again \(c\), but \(c\) is not saturated by \(N\). Since an \(N\)-perfect flower would have to start at the base of this only blossom with an edge of \(N\), and no edge of \(N\) is incident with \(c\), no \(N\)-perfect flower exists. This proves the proposition. Notice also that this graph is not \(2\)-bicritical in the sense of Pulleyblank–Larson: for the independent set \(\{e\}\) one has \(N(\{e\})=\{d\}\), and hence \(|N(\{e\})|=|\{e\}|\). ◻
We collect the examples that motivate the hypotheses and the role of the core.
Example 7.1(A König–Egerváry graph with a non-defective perfect flower.).Let \(G\) be the triangle \(abc\) with a leaf \(d\) attached to \(c\). Then \[\alpha(G)=2,\qquad \mu(G)=2,\] so \(G\) is Kőnig–Egerváry. With respect to the perfect matching \(M=\{ab,cd\}\), the triangle \(abc\) together with the path \(c,d\) is an \(M\)-perfect flower. However, the only odd-distance vertex on the path is \(d\), and \[\operatorname{core}(G)=\{d\}.\]
Thus the perfect flower is not core-defective. This example shows that the word “core-defective” cannot be omitted.
Example 7.2(A matchable non-König–Egerváry graph).Let \(G\) consist of two triangles \(abc\) and \(def\) joined by the edge \(cd\). The matching \[M=\{ab,cd,ef\},\] is perfect. Since \(\alpha(G)=2\) and \(\mu(G)=3\), we have \[\alpha(G)+\mu(G)=5<6=|V(G)|,\] so \(G\) is not Kőnig–Egerváry. The triangle \(abc\) together with the path \(c,d\) is an \(M\)-perfect flower. The vertex \(d\) is at distance one from the joint \(c\), and \(d\notin\operatorname{core}(G)\). Hence this is a core-defective perfect flower, in agreement with Theorem 4.1.
Example 7.3(A switching example for an ordinary flower). Let \(G\) have vertex set \[\{a,b,x,y,r,p,q\},\] and edge set \[\{ab,bx,xa,xy,yr,xr,rp,pq,aq,bq\}.\]
Take \[M=\{ab,xy,pq\}.\]
Then \(M\) is maximum, \(\mu(G)=3\), and the maximum independent sets are exactly \[\{a,y,p\},\qquad \{b,y,p\}.\]
Thus \(\alpha(G)=3\), \(\operatorname{core}(G)=\{y,p\}\), and \(\alpha(G)+\mu(G)=6<7=|V(G)|\).
The triangle \(C=abx\) is an \(M\)-blossom based at \(x\), and \[S=x,y,r,\] is an \(M\)-stem whose root \(r\) is \(M\)-unsaturated. The direct perfect-flower prefix \((C,x,y)\) is not core-defective, because its only odd-side vertex is \(y\in\operatorname{core}(G)\). This is the situation in which the switching part of Lemma 5.4 is needed.
Switching along the whole stem gives \[N=M\triangle E(S)=\{ab,yr,pq\}.\]
Now \(x\) is an exposed base of the blossom \(C\). The one-edge path \(R=x,r\) is an odd \(N\)-exit from \(C\), and \(r\notin\operatorname{core}(G)\). Lemma 5.1 switches this exit and deletes the \(N\)-mate \(ry\) of \(r\), producing the maximum matching \[M'=\{ab,xr,pq\}.\]
With respect to \(M'\), the pair \((C,x,r)\) is a core-defective perfect flower. This example illustrates why Lemmas 5.1–5.4 are needed beyond the direct posy and two-triangle cases.
Example 7.4(Odd cycles).An odd cycle \(C_{2r+1}\) is not Kőnig–Egerváry, because \[\alpha(C_{2r+1})=r, \qquad \mu(C_{2r+1})=r, \qquad |C_{2r+1}|=2r+1.\]
However, it has no perfect flower. Indeed, for any maximum matching, the whole cycle is a blossom with an unsaturated base, but there is no vertex outside the cycle through which a non-trivial attaching path can start. Thus odd cycles are the unavoidable connected exception in Theorem 5.5.
Example 7.5(A disconnected obstruction).The graph \(C_3\cup K_1\) is not Kőnig–Egerváry, since \[\alpha(C_3\cup K_1)=2, \qquad \mu(C_3\cup K_1)=1, \qquad |C_3\cup K_1|=4.\]
It is not \(2\)-bicritical, because the isolated vertex \(u\) satisfies \(N(\{u\})=\varnothing\). Nevertheless, no maximum matching gives a perfect flower: the only odd cycle is the triangle, and its base is unsaturated with no matching edge leaving it. This example explains why connectedness is necessary in Theorem 5.5.
Theorem 4.1 converts Sterboul’s flower-posy obstruction into a core statement in the matchable case; for posies, this conversion uses the clean representative supplied by Lemma 3.4. Theorem 5.5 and Corollary 5.6 give the corresponding connected and component-wise forms when perfect matchings are not assumed.
It is useful to separate the local and global parts of the obstruction. The structural part of a core-defective perfect flower is local: an odd blossom, an alternating attaching path, and a specified odd-distance vertex on that path. The assertion that this vertex is outside \(\operatorname{core}(G)\) is global, because it refers to all maximum independent sets. Thus the local flower data alone should not be advertised as a purely local certificate of non-membership in the core. If one also provides a maximum independent set \(I\) avoiding the specified odd-side vertex, together with an independent verification that \(I\) has maximum cardinality, then the global condition \(z\notin\operatorname{core}(G)\) is certified as well.
The connection with the perfect-flower decomposition used in determinant and permanent factorizations [15] should be viewed as motivation rather than as a new matrix-theoretic consequence proved here. In a Kőnig–Egerváry graph, perfect flowers are not forbidden; rather, their odd path vertices are forced into the core. In a non-Kőnig–Egerváry graph with a perfect matching, this core constraint fails for every maximum matching. Developing concrete determinant or permanent consequences from this failure is a natural direction for future work.
The general case without perfect matchings is subtler only with respect to the quantifier over maximum matchings. Theorem 5.5 proves the existential characterization for connected graphs, and Corollary 5.6 explains how disconnected graphs decompose component by component. However, Proposition 6.1 shows that the universal quantifier over maximum matchings cannot be rescued without additional hypotheses: a connected non-Kőnig–Egerváry graph with no perfect matching may have one maximum matching that yields a core-defective perfect flower and another maximum matching that yields no perfect flower at all.
We have proved a new characterization of connected Kőnig–Egerváry graphs in terms of perfect flowers and the core. Apart from the unavoidable odd-cycle exception, a connected graph is non-Kőnig–Egerváry if and only if it contains a core-defective perfect flower. Equivalently, among connected graphs different from an odd cycle, the Kőnig–Egerváry graphs are precisely those graphs in which every perfect flower is core-forced: all odd-distance vertices on the attaching path lie in the core.
In the presence of a perfect matching the statement strengthens to a clean quantifier theorem: a matchable graph is non-Kőnig–Egerváry if and only if some, equivalently every, maximum matching admits a core-defective perfect flower. Thus the perfect-matching hypothesis is not needed for the existential characterization, but it is exactly what makes the universal quantifier over maximum matchings valid.
The examples show that each hypothesis has a role. Perfect flowers alone do not characterize non-Kőnig–Egerváry graphs, because Kőnig–Egerváry graphs may contain non-defective perfect flowers. Odd cycles are non-Kőnig–Egerváry but have no perfect flowers. Disconnected graphs are handled component by component, while graphs without perfect matchings still require care because the universal quantifier over maximum matchings may fail.
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.