Let \(\alpha(G)\), \(\mu(G)\) and prk\((G)\) denote the independence number, the matching number and the permanental rank of \(G\), respectively. Here prk\((G)\) is the maximum order of a principal submatrix with nonzero permanent of the adjacency matrix of \(G\). Let \(d(G)=\max_{S\subseteq V(G)}\{|S|-|N(S)|\}\) be the critical difference of \(G\). Let core\((G)\) and ker\((G)\) be the intersection of all maximum independent sets and all critical independent sets, respectively. In this note we use Larson’s critical independence decomposition to split the graph into two induced subgraphs, \(L_G\) and \(L_G^c\), where \(L_G\) is Kőnig–Egerváry and \(L_G^c\) is 2-bicritical. We prove that for every graph \(G\) one has \(\alpha(G)-\mu(G) = |L_G|-prk(L_G)+\alpha(L_G^c)-\mu(L_G^c) = d(L_G)+\alpha(L_G^c)-\mu(L_G^c).\) Moreover, we show that \(\alpha(L_G^c)\le \mu(L_G^c)\) and establish the refined kernel bound \(d(L_G)+k\le |ker(G)|,\) where \(k\) is the number of nontrivial connected components of \(L_G\) without a perfect matching. Consequently, \(\alpha(G)-\mu(G)+k\le |ker(G)|.\) In particular, when \(\alpha(G)>\mu(G)\), one has \(|L_G|>prk(L_G)\). The bound is sharp for every prescribed value of \(k\). Since ker\((G)\subseteq core(G)\) for every graph, we recover as a consequence the known Boros–Golumbic–Levit inequality \(\alpha(G)-\mu(G)+1\le |core(G)|\) for connected graphs with at least two vertices and \(\alpha(G)>\mu(G)\). This result improves on related results by Hammer et al. (1982) and by Levit and Mandrescu (1999).
Let \(\alpha(G)\) denote the cardinality of a maximum independent set, and let \(\mu(G)\) be the size of a maximum matching in \(G=(V,E)\). A graph \(G\) is a Kőnig–Egerváry graph if \[\alpha(G)+\mu(G)=|V(G)|.\]
Kőnig–Egerváry graphs have been extensively studied [4, 9, 34, 3, 14, 20, 21, 15]. Every bipartite graph is Kőnig–Egerváry [7]. These graphs were independently introduced by Deming [4], Sterboul [34], and Gavril [9].
The notion of \(2\)-bicritical graphs was introduced in [31], and they can be characterized as follows.
Theorem 1.1. ([31]). A graph \(G\) is \(2\)-bicritical if and only if \(|N(S)|>|S|\) for every nonempty independent set \(S\subseteq V(G)\).
The class of \(2\)-bicritical graphs can be regarded as the structural counterpart of Kőnig–Egerváry graphs [17, 30, 28, 27]. Pulleyblank proved that almost every graph is \(2\)-bicritical [31].
The main tool used in this work is Larson’s critical independence decomposition [17]. It partitions a graph into a part \(L_G\) inducing a Kőnig–Egerváry graph and a complementary part \(L_G^c\) inducing a \(2\)-bicritical graph.
Let \[\Omega^{*}(G)=\{S:S\text{ is an independent set of }G\},\] and \[\Omega(G)=\{S:S\text{ is a maximum independent set of }G\},\] and \[\text{core}(G)=\bigcap\{S:S\in\Omega(G)\},\] [19]. For \(X\subseteq V(G)\), put \(d_G(X)=|X|-|N_G(X)|\), and define \[d(G)=\max\{d_G(X):X\subseteq V(G)\}.\]
The number \(d(G)\) is the critical difference of \(G\), and a set \(U\subseteq V(G)\) is critical if \(d_G(U)=d(G)\) [35]. The critical independence difference is \[d_I(G)=\max\{d_G(X):X\in\Omega^{*}(G)\}.\]
If \(X\in\Omega^{*}(G)\) satisfies \(d_G(X)=d_I(G)\), then \(X\) is called a critical independent set. It is known that \(d(G)=d_I(G)\) for every graph [35]. We write \[\text{CritIndep}(G)=\{S:S\text{ is a critical independent set of }G\},\] and \[\text{MaxCritIndep}(G)=\{S:S\text{ is a maximum critical independent set of }G\},\] and \[\text{ker}(G)=\bigcap\text{CritIndep}(G),\] [22, 24, 33]. Every critical independent set is contained in a maximum critical independent set, and a maximum critical independent set can be found in polynomial time [16].
Let \(k\) be the number of nontrivial connected components of \(L_G\) without a perfect matching. The main new contributions of this note are the exact Larson-decomposition formula \[\begin{aligned} \alpha(G)-\mu(G) = & |L_G|-\text{prk}(L_G)+\alpha(L_G^c)-\mu(L_G^c)\\ = & d(L_G)+\alpha(L_G^c)-\mu(L_G^c), \end{aligned}\] the inequality \(\alpha(L_G^c)\le \mu(L_G^c)\), and the refined kernel bound \[d(L_G)+k\le |\text{ker}(G)|.\]
In particular, since \(\alpha(G)-\mu(G)\le d(L_G)\), this gives \[\alpha(G)-\mu(G)+k\le |\text{ker}(G)|.\]
The parameter \(k\) is polynomial-time computable. Since \(\text{ker}(G)\subseteq \text{core}(G)\) for every graph [22], every lower bound obtained here for \(|\text{ker}(G)|\) also gives a lower bound for \(|\text{core}(G)|\). In this way the present approach recovers, as a known consequence, the theorem of Boros, Golumbic and Levit stating that \(\alpha(G)-\mu(G)+1\le |\text{core}(G)|\) for connected graphs with at least two vertices and \(\alpha(G)>\mu(G)\) [2]. It also gives a structural refinement of earlier lower bounds for \(|\text{core}(G)|\) due to Hammer, Hansen and Simeone [12] and to Levit and Mandrescu [18]. Related results for trees were obtained by Zito [36] and by Gunther, Hartnell and Rall [10].
The approach combines Larson’s critical independence decomposition, matching theory, the Gallai–Edmonds decomposition and Sachs subgraphs. The paper is organized as follows. In Section 2 we recall terminology and auxiliary results. Section 3 contains the decomposition formula for \(\alpha(G)-\mu(G)\), the refined lower bound for \(|\text{ker}(G)|\), the sharpness construction, and the polynomial-time computability of \(k\).
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 [25] 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 \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\).
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)\).
The number of vertices in a graph \(G\) is called the order of the graph and denoted by \(\left|G\right|\) or \(n(G)\). A cycle in \(G\) is called odd (resp. even) if it has an odd (resp. even) number of edges.
For a vertex \(v\in V(G)\), the neighborhood of \(v\) is \[N_G(v)=\{u\in V(G): uv\in E(G)\}.\]
When no confusion arises, we write \(N(v)\) instead of \(N_G(v)\). For a set \(S\subseteq V(G)\), the neighborhood of \(S\) is \[N_G(S)=\bigcup_{v\in S} N_G(v).\]
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\). Matchings induce an involution on the vertex set of the graph: \(M:V(G)\rightarrow V(G)\), where \(M(v)=u\) if \(uv \in M\), and \(M(v)=v\) otherwise. If \(S, U \subseteq V(G)\) with \(S \cap U = \emptyset\), we say that \(M\) is a matching from \(S\) to \(U\) if \(M(S) \subseteq U\). A matching \(M\) is perfect if \(M(v)\neq v\) for every vertex of the graph. A matching is near-perfect if \(\left|{v \in V(G) : M(v) = v}\right| = 1\). The matching deficiency of \(G\) is \[\text{def}(G)=|V(G)|-2\mu(G),\] that is, the number of vertices left unmatched by any maximum matching. This notation is distinct from the Gallai–Edmonds set \(D(G)\) defined below. A graph is a factor-critical graph if \(G-v\) has perfect matching for every vertex \(v\in V(G)\).
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)\). A bipartite graph is a graph whose vertex set can be partitioned into two disjoint independent sets.
The Gallai–Edmonds decomposition will play an important role in this work
Theorem 2.1. ([6, 8] Gallai–Edmonds structure theorem). Let \(G\) be a graph, and define \[\begin{aligned} & D(G):= \{ v : \text{there exists a maximum matching that misses } v \}, \\ &A(G) := \{ v : v \text{ is adjacent to some } u \in D(G), \text{ but } v \notin D(G) \}, \\ & C(G):= V(G) – (D(G) \cup A(G)). \end{aligned}\]
If \(G_{1}, \dots, G_{k}\) are the connected components of \(G[D(G)]\) and \(M\) is a maximum matching of \(G\), then:
(a) \(M\) covers \(C(G)\) and matches \(A(G)\) into distinct components of \(G[D(G)]\).
(b) Each \(G_i\) is a factor-critical graph, and the restriction of \(M\) to \(G_i\) is a near-perfect matching.
(c) Each nonempty \(S\subseteq A(G)\) is adjacent to at least \(|S|+1\) components of \(G[D(G)]\).
We also recall the classical Hall’s theorem.
Theorem 2.2. ([11]). Let \(G\) be a bipartite graph with bipartition \((A,B)\). Then there exists a matching that saturates \(A\) if and only if \[|N(S)|\ge |S|,\] for every subset \(S\subseteq A\).
In this section we establish the main results of the paper by means of Larson’s decomposition. In particular, we derive a new expression for \(\alpha(G)-\mu(G)\) and obtain new lower bounds for \(|\text{ker}(G)|\). Before starting, we need to introduce some necessary tools and notation. In [17], Larson introduces the following decomposition theorem.
Theorem 3.1. ([17]). For any graph \(G\), there is a unique set \(L(G)\subset V(G)\) such that
(a) \(\alpha(G)=\alpha(G[L(G)])+\alpha(G[V(G)-L(G)])\),
(b) \(G[L(G)]\) is a Kőnig–Egerváry graph,
(c) for every non-empty independent set \(I\) in \(G[V(G)-L(G)]\), we have \(|N_{G[V(G)-L(G)]}(I)|>|I|\), and
(d) for every maximum critical independent set \(J\) of \(G\), \(L(G)=J\cup N_G(J)\).
Throughout the remainder of the paper, \(L(G)\) and \(L^{c}(G)=V(G)-L(G)\) denote the sets of Theorem 3.1; moreover, to simplify the notation, we define the induced graphs \[\begin{aligned} L_{G} & :=G[L(G)],\\ L_{G}^{c} & :=G[L^{c}(G)]. \end{aligned}\]
Lemma 3.2. ([16]). Every critical independent set is contained in a maximum critical independent set.
Observation 3.3. By Theorem 3.1, for every graph \(G\) with \(L^c(G)\neq \emptyset\), it follows that \(L_{G}^{c}\) is a 2-bicritical graph.
Lemma 3.4. ([16]). 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\).
Corollary 3.5. For every graph \(G\), \[\mu(G)=\mu(L_G)+\mu(L_G^c).\]
Proof. Let \(I\in\text{MaxCritIndep}(G)\). By Theorem 3.1, \(L(G)=I\cup N_G(I)\). Hence \(I\) has no neighbors in \(L^c(G)\), and every edge of \(G\) meeting \(I\) has its other endpoint in \(N_G(I)\). By Lemma 3.4, there is a matching in \(G\) saturating \(N_G(I)\) into \(I\); all its edges belong to \(L_G\). Therefore \(\mu(L_G)\ge |N_G(I)|\). Conversely, since \(I\) is independent and \(L(G)=I\cup N_G(I)\), every edge of \(L_G\) is incident with at least one vertex of \(N_G(I)\); hence every matching of \(L_G\) has size at most \(|N_G(I)|\). Thus \[\mu(L_G)=|N_G(I)|.\]
Now let \(M\) be any matching of \(G\). Each edge of \(M\) that is not contained in \(L_G^c\) and has an endpoint in \(L(G)\) must use a distinct vertex of \(N_G(I)\); hence there are at most \(|N_G(I)|=\mu(L_G)\) such edges. The edges of \(M\) contained in \(L_G^c\) form a matching of \(L_G^c\), so there are at most \(\mu(L_G^c)\) of them. It follows that \(|M|\le \mu(L_G)+\mu(L_G^c)\).
For the reverse inequality, take a maximum matching of \(L_G\) saturating \(N_G(I)\) into \(I\) and a maximum matching of \(L_G^c\). These two matchings are vertex-disjoint, and their union is a matching of \(G\) of size \(\mu(L_G)+\mu(L_G^c)\). Therefore \(\mu(G)=\mu(L_G)+\mu(L_G^c)\). \(\square\)
A spanning subgraph of a graph \(G\) is called a Sachs subgraph if each of its components is a regular graph of degree one or two. Equivalently, each component is an edge \(K_2\) or a cycle. Such subgraphs arise naturally in the study of determinants and permanents of adjacency matrices [13, 26, 32]. They are also known as \(\{1,2\}\)-factors and are closely related to perfect \(2\)-matchings. Note that every perfect matching is a Sachs subgraph, since all its components are copies of \(K_2\). The set of all Sachs subgraphs of \(G\) is denoted by \(\text{Sachs}(G)\).
For \(X\subseteq V(G)\), let \(A_G[X]\) be the principal submatrix of the adjacency matrix of \(G\) indexed by \(X\). The permanent \(\text{perm}(A_G[X])\) is nonzero if and only if there is a permutation \(\sigma\) of \(X\) such that \(x\sigma(x)\in E(G)\) for every \(x\in X\). The cycles of such a permutation produce a spanning Sachs subgraph of the induced graph \(G[X]\): cycles of length two produce \(K_2\) components and cycles of length at least three produce graph cycles. Conversely, every spanning Sachs subgraph of \(G[X]\) gives such a permutation. Therefore \[\text{prk}(G)=\max\{|X|:X\subseteq V(G)\text{ and }\text{Sachs}(G[X])\neq\emptyset\}.\]
This is the same as the maximum order of a subgraph of \(G\) admitting a spanning Sachs subgraph, because any such subgraph is contained in the corresponding induced subgraph.
We define \[\text{Sachs}^{\text{prk}}(G):=\bigcup_{H}\text{Sachs}(H),\] where the union is taken over all induced subgraphs \(H\) of \(G\) of order \(\text{prk}(G)\). If \(\text{Sachs}(G)\neq\emptyset\), then \(\text{Sachs}^{\text{prk}}(G)=\text{Sachs}(G)\).
Lemma 3.6. ([29]). Let \(G\) be a Kőnig–Egerváry graph and \(H\in\text{Sachs}^{\text{prk}}(G)\). Then \(H\) has no odd cycles.
Corollary 3.7. Let \(G\) be a Kőnig–Egerváry graph. Then \(\text{prk}(G)=2\mu(G)\).
Proof. Let \(H\in\text{Sachs}^{\text{prk}}(G)\). By Lemma 3.6, \(H\) has no odd cycles. Hence each component of \(H\) is either a copy of \(K_2\) or an even cycle, and so \(H\) has a perfect matching. Therefore \(|H|/2\le \mu(G)\), which gives \(\text{prk}(G)\le 2\mu(G)\). Conversely, a maximum matching of \(G\) is a Sachs subgraph on \(2\mu(G)\) vertices. Thus \(\text{prk}(G)\ge 2\mu(G)\), and equality follows. \(\square\)
Observation 3.8. If \(G\) is a Kőnig–Egerváry graph, then \(\alpha(G)-\mu(G)=\text{def}(G)\).
Proof. Since \(G\) is Kőnig–Egerváry, \(\alpha(G)+\mu(G)=|V(G)|\). Hence \[\alpha(G)-\mu(G)=|V(G)|-2\mu(G)=\text{def}(G).\] \(\square\)
Theorem 3.9. ([23]). If \(G\) is a Kőnig–Egerváry graph, then \[\alpha(G)-\mu(G)=d(G).\]
Corollary 3.10. If \(G\) is a Kőnig–Egerváry graph, then \(d(G)=\text{def}(G)\).
Proof. By definition, \(\text{def}(G)=|V(G)|-2\mu(G)\). Since \(G\) is Kőnig–Egerváry, \(\alpha(G)+\mu(G)=|V(G)|\), and therefore \[\alpha(G)-\mu(G)=\text{def}(G).\]
By the preceding theorem, \(d(G)=\alpha(G)-\mu(G)\); hence \(d(G)=\text{def}(G)\). \(\square\)
Theorem 3.11. ([1]). An independent set \(S\) is maximum if and only if every independent set disjoint from \(S\) can be matched into \(S\).
We now arrive at the first main result of the section. The next theorem shows that the quantity \(\alpha(G)-\mu(G)\) can be read directly from the Larson decomposition. More precisely, it shows that the contribution coming from the Kőnig–Egerváry side \(L_G\) admits two equivalent descriptions: one in terms of the permanental rank of \(L_G\), and another in terms of its critical difference.
Theorem 3.12. For every graph \(G\) it holds that \[\begin{aligned} \alpha(G)-\mu(G) = & \left|L_{G}\right|-\text{prk}(L_{G})+\alpha\left(L_{G}^{c}\right)-\mu\left(L_{G}^{c}\right)\\ = & d(L_{G})+\alpha\left(L_{G}^{c}\right)-\mu\left(L_{G}^{c}\right). \end{aligned}\]
Proof. By Theorem 3.1 and Corollary 3.5, \[\alpha(G)-\mu(G)=\alpha(L_G)-\mu(L_G)+\alpha(L_G^c)-\mu(L_G^c).\]
We first identify the term coming from \(L_G\). Let \(I\in\text{MaxCritIndep}(G)\). By Theorem 3.1, \(L(G)=I\cup N_G(I)\). Since \(I\) is independent, every edge of \(L_G\) is incident with a vertex of \(N_G(I)\). By Lemma 3.4, there is a matching of \(L_G\) saturating \(N_G(I)\) into \(I\); hence \[\mu(L_G)=|N_G(I)|.\]
Moreover, \(L_G\) is Kőnig–Egerváry by Theorem 3.1; therefore \[\alpha(L_G)=|L_G|-\mu(L_G)=|I|+|N_G(I)|-|N_G(I)|=|I|,\] so \(I\in\Omega(L_G)\).
Since \(L_G\) is Kőnig–Egerváry, Corollary 3.7 gives \(\text{prk}(L_G)=2\mu(L_G)\). Thus \[|L_G|-\text{prk}(L_G)=|L_G|-2\mu(L_G)=\alpha(L_G)-\mu(L_G),\] where the last equality again uses \(\alpha(L_G)+\mu(L_G)=|L_G|\). Also, by Theorem 3.9, \[d(L_G)=\alpha(L_G)-\mu(L_G).\]
Substituting these two identities in the first displayed equality gives \[\begin{aligned} \alpha(G)-\mu(G) = & |L_G|-\text{prk}(L_G)+\alpha(L_G^c)-\mu(L_G^c)\\ = & d(L_G)+\alpha(L_G^c)-\mu(L_G^c), \end{aligned}\] as required. \(\square\)
Theorem 3.12 shows that the term coming from \(L_G^c\) remains to be controlled. The next observation shows that this contribution is never positive; this is an immediate consequence of Theorem 2.2 and Theorem 3.1.
Remark 3.13. For every graph \(\alpha(L_{G}^{c})\le\mu(L_{G}^{c})\).
Proof. Let \(I\in\Omega(L_G^c)\). For every nonempty set \(S\subseteq I\), the set \(S\) is an independent set of \(L_G^c\); hence Theorem 3.1 gives \[|N_{L_G^c}(S)|>|S|.\]
The same Hall inequality is trivial for \(S=\emptyset\). Consider the bipartite graph with parts \(I\) and \(N_{L_G^c}(I)\) and with the edges induced by \(L_G^c\) between these two parts. By Theorem 2.2, this bipartite graph has a matching saturating \(I\). Therefore \[\mu(L_G^c)\ge |I|=\alpha(L_G^c),\] as claimed. \(\square\)
Corollary 3.14. For every graph \(G\), \[\alpha(G)-\mu(G)\le d(L_G)=|L_G|-\text{prk}(L_G).\]
Moreover, equality holds if and only if \(\alpha(L_G^c)=\mu(L_G^c).\)
Proof. By Theorem 3.12, \[\alpha(G)-\mu(G)=d(L_G)+\alpha(L_G^c)-\mu(L_G^c).\]
Since Remark 3.13 gives \(\alpha(L_G^c)\le \mu(L_G^c),\) the inequality follows immediately. The equality statement is also immediate. \(\square\)
Lemma 3.15. Let \(G\) be a graph with \(\alpha(G)>\mu(G)\). Then \(|L_G|>\text{prk}(L_G)\).
Proof. By Theorem 3.12, \[\alpha(G)-\mu(G)=d(L_G)+\alpha(L_G^c)-\mu(L_G^c).\]
Since Remark 3.13 gives \(\alpha(L_G^c)\le \mu(L_G^c)\) and \(\alpha(G)>\mu(G)\), we must have \(d(L_G)>0\). By Theorem 3.12, \(d(L_G)=|L_G|-\text{prk}(L_G)\), and the conclusion follows. \(\square\)
Lemma 3.16. Let \(G\) be a connected graph with at least two vertices and \(\alpha(G)>\mu(G)\). Then \(L_G\) has at least one nontrivial connected component without a perfect matching.
Proof. By Lemma 3.15, \(d(L_G)=|L_G|-\text{prk}(L_G)>0\). Since \(L_G\) is Kőnig–Egerváry, this is equivalent to \(\alpha(L_G)>\mu(L_G)\). Thus \(L_G\) has no perfect matching: if it had one, then \(\mu(L_G)=|L_G|/2\) and every independent set would contain at most one endpoint of each matching edge, giving \(\alpha(L_G)\le |L_G|/2=\mu(L_G)\).
It remains to show that \(L_G\) has no isolated vertices. Let \(I\in\text{MaxCritIndep}(G)\). By Theorem 3.1, \(L(G)=I\cup N_G(I)\). If \(v\) is an isolated vertex of \(L_G\), then \(v\notin N_G(I)\), because every vertex of \(N_G(I)\) is adjacent in \(L_G\) to a vertex of \(I\). Hence \(v\in I\). Since all neighbors of vertices of \(I\) lie in \(N_G(I)\subseteq L(G)\), the fact that \(v\) is isolated in \(L_G\) implies that \(v\) is isolated in \(G\), contradicting that \(G\) is connected and has at least two vertices. Therefore \(L_G\) has no trivial connected components. Since \(L_G\) has no perfect matching, at least one of its connected components has no perfect matching, and this component is nontrivial. \(\square\)
We now turn this structural information into a new lower bound for \(|\text{ker}(G)|\). The next theorem proves the stronger form suggested by the Larson side of the decomposition: the term \(d(L_G)\) can be lifted to \(|\text{ker}(G)|\), and every nontrivial connected component of \(L_G\) without a perfect matching contributes one additional vertex.
Theorem 3.17. For every graph \(G\), \[d(L_G)+k\le |\text{ker}(G)|,\] where \(k\) is the number of nontrivial connected components of \(L_G\) without a perfect matching. Consequently, \[\alpha(G)-\mu(G)+k\le |\text{ker}(G)|.\]
Proof. Put \(H=L_G\). For a matching \(M\) of \(H\), write \[U(M)=\{v\in V(H):M(v)=v\},\] for the set of vertices not saturated by \(M\).
Claim 1. If \(M\) is a maximum matching of \(H\), then \(U(M)\subseteq \text{ker}(G)\).
Proof. Let \(S\in\text{CritIndep}(G)\) be arbitrary. By Lemma 3.2, there exists \(J\in\text{MaxCritIndep}(G)\) such that \(S\subseteq J\). By Theorem 3.1, \[L(G)=J\cup N_G(J).\]
In particular, \(S\subseteq L(G)\) and \(N_G(S)\subseteq N_G(J)\subseteq L(G)\). Hence the neighborhood of \(S\) does not change when it is considered inside \(H\): \[N_H(S)=N_G(S).\]
Therefore \[d_H(S)=|S|-|N_H(S)|=|S|-|N_G(S)|=d_G(S).\]
Since \(S\) is critical independent, \(d_G(S)=d_I(G)\).
We now compute the deficiency of \(H\). Since \(J\) is independent and \(V(H)=J\cup N_G(J)\), every edge of \(H\) is incident with at least one vertex of \(N_G(J)\). Thus every matching of \(H\) has size at most \(|N_G(J)|\). On the other hand, by Lemma 3.4 there exists a matching saturating \(N_G(J)\) into \(J\), and this matching is contained in \(H\). Consequently, \(\mu(H)=|N_G(J)|.\)
It follows that \[\begin{aligned} \text{def}(H) = & |V(H)|-2\mu(H)\\ = & |J|+|N_G(J)|-2|N_G(J)|\\ = & |J|-|N_G(J)|\\ = & d_G(J)\\ = & d_I(G). \end{aligned}\]
Combining this with \(d_H(S)=d_G(S)=d_I(G)\) gives \[d_H(S)=\text{def}(H).\]
Let \(M\) be a maximum matching of \(H\). Since \(S\) is independent, each vertex of \(S\) saturated by \(M\) must be matched to a distinct vertex of \(N_H(S)\). Thus \(M\) saturates at most \(|N_H(S)|\) vertices of \(S\), and hence it leaves at least \[|S|-|N_H(S)|=d_H(S)=\text{def}(H),\] vertices of \(S\) unsaturated. But a maximum matching of \(H\) leaves exactly \(\text{def}(H)\) vertices of \(H\) unsaturated. Therefore all vertices of \(H\) left unsaturated by \(M\) belong to \(S\), that is, \(U(M)\subseteq S\).
Since \(S\in\text{CritIndep}(G)\) was arbitrary, we obtain \[U(M)\subseteq \bigcap_{S\in\text{CritIndep}(G)}S=\text{ker}(G).\]
This proves the claim. \(\square\)
Let \(C_1,\ldots,C_k\) be the nontrivial connected components of \(H\) without a perfect matching. Take a maximum matching \(M\) of \(H\). Then \[|U(M)|=\text{def}(H),\] and by Claim 1 \(U(M)\subseteq\text{ker}(G)\).
Fix \(i\in\{1,\ldots,k\}\). Since \(C_i\) has no perfect matching, the restriction of \(M\) to \(C_i\) leaves some vertex \(x_i\in V(C_i)\) unsaturated. The component \(C_i\) is nontrivial and connected, so \(x_i\) has a neighbor \(y_i\in V(C_i)\). The vertex \(y_i\) must be saturated by \(M\); otherwise the edge \(x_iy_i\) could be added to \(M\), contradicting the maximality of \(M\). Let \[z_i=M(y_i).\]
Then \(z_i\notin U(M)\). Define \[M_i'=(M-\{y_iz_i\})\cup\{x_iy_i\}.\]
This is again a maximum matching of \(H\), because it has the same number of edges as \(M\). Moreover, \(M_i'\) leaves \(z_i\) unsaturated. Applying Claim 1 to \(M_i'\) gives \(z_i\in\text{ker}(G)\).
Repeating this argument for \(i=1,\ldots,k\), we obtain vertices \(z_1,\ldots,z_k\in\text{ker}(G)\). They are pairwise distinct, because they belong to distinct connected components \(C_i\), and none of them belongs to \(U(M)\). Hence \[U(M)\cup\{z_1,\ldots,z_k\}\subseteq\text{ker}(G),\] and therefore \[|\text{ker}(G)|\ge |U(M)|+k=\text{def}(H)+k.\]
Since \(H=L_G\) is Kőnig–Egerváry, Corollary 3.10 gives \(\text{def}(H)=d(H)=d(L_G)\). Thus \[d(L_G)+k\le |\text{ker}(G)|.\]
Finally, Theorem 3.12 and Remark 3.13 give \(\alpha(G)-\mu(G)\le d(L_G)\), and consequently \[\alpha(G)-\mu(G)+k\le |\text{ker}(G)|.\] \(\square\)
For a Kőnig–Egerváry graph \(G\), Larson’s decomposition is trivial, that is, \(L(G)=V(G)\). Hence we obtain the following consequence.
Corollary 3.18. Let \(G\) be a Kőnig–Egerváry graph and let \(k\) be the number of nontrivial connected components of \(G\) without a perfect matching. Then \[d(G)+k\le |\text{ker}(G)|.\]
Equivalently, \(\alpha(G)-\mu(G)+k\le |\text{ker}(G)|\).
Proof. Since \(G\) is Kőnig–Egerváry, \(L_G=G\) and \(d(G)=\alpha(G)-\mu(G)\) by the Levit–Mandrescu theorem. The result follows from Theorem 3.17. \(\square\)
Corollary 3.19. If \(|\text{ker}(G)|=\alpha(G)-\mu(G)\), then every nontrivial connected component of \(L_G\) has a perfect matching.
Proof. Let \(k\) be the number of nontrivial connected components of \(L_G\) without a perfect matching. By Theorem 3.17, \(d(L_G)+k\le |\text{ker}(G)|\), while Theorem 3.12 and Remark 3.13 imply \(\alpha(G)-\mu(G)\le d(L_G)\). Therefore, \[\alpha(G)-\mu(G)+k\le d(L_G)+k\le |\text{ker}(G)|=\alpha(G)-\mu(G).\]
Thus \(k=0\), which is precisely the assertion. \(\square\)
Corollary 3.20. Let \(t\ge 0\) be an integer. If \[\alpha(G)>\frac{\left|G\right|+t-1}{2},\] then \[|\text{ker}(G)|\ge t+k,\] where \(k\) is the number of nontrivial connected components of \(L_G\) without a perfect matching.
Proof. Since \(\mu(G)\le \left|G\right|-\alpha(G)\), we have \[\alpha(G)-\mu(G)\ge 2\alpha(G)-\left|G\right|.\]
Hence, from \[\alpha(G)>\frac{\left|G\right|+t-1}{2},\] it follows that \[\alpha(G)-\mu(G)>t-1.\]
Since \(\alpha(G)-\mu(G)\) is an integer, we get \[\alpha(G)-\mu(G)\ge t.\]
The conclusion now follows from Theorem 3.17. \(\square\)
We now pass from \(\text{ker}(G)\) to \(\text{core}(G)\). Since \(\text{ker}(G)\) is always contained in \(\text{core}(G)\), the lower bounds obtained above for \(|\text{ker}(G)|\) can be transferred to \(|\text{core}(G)|\). In this way, the Larson decomposition yields a short and transparent structural route to a known inequality of Boros, Golumbic, and Levit. We record this consequence next.
Theorem 3.21. ([22]). For every graph \(G\), we have \(\text{ker}(G)\subseteq\text{core}(G)\).
Theorem 3.22. ([2]). If \(G\) is a connected graph with at least two vertices and \(\alpha(G)>\mu(G)\), then \(\alpha(G)-\mu(G)+1\le\left|\text{core}(G)\right|.\)
Proof. Let \(k\) be the number of nontrivial connected components of \(L_{G}\) without a perfect matching. By Lemma 3.16 \(k\ge1\), then by Theorem 3.21 \(\left|\text{ker}(G)\right|\le\left|\text{core}(G)\right|\) and by Theorem 3.17 \[\alpha(G)-\mu(G)+1\le\alpha(G)-\mu(G)+k\le\left|\text{ker}(G)\right|\le\left|\text{core}(G)\right|.\]
As we wanted to prove. \(\square\)
The edge set consists of \[\{a_ix_i,b_ix_i,x_ir:1\le i\le k\}\cup\{rs,st,tr\}.\]
Thus the vertices \(a_i,x_i,b_i\) induce a copy of \(P_3\) for each \(i\), and the vertices \(r,s,t\) induce a triangle. Let \[L_k=\{a_i,b_i,x_i:1\le i\le k\}.\]
Then \(G_k[L_k]=kP_3\) is Kőnig–Egerváry and \(G_k[V(G_k)-L_k]=K_3\) is \(2\)-bicritical. Moreover, \[\alpha(G_k)=2k+1=\alpha(kP_3)+\alpha(K_3).\]
Indeed, every independent set contains at most two vertices from each triple \(\{a_i,b_i,x_i\}\), and replacing \(x_i\) by the two leaves \(a_i,b_i\) never decreases the size of an independent set. Hence a maximum independent set contains all leaves \(a_i,b_i\) and one vertex of the triangle.
Let \[A=\{a_i,b_i:1\le i\le k\},\qquad X=\{x_i:1\le i\le k\},\qquad T=\{r,s,t\}.\]
Then \(d_{G_k}(A)=|A|-|X|=k\). We now determine the critical independent sets directly. Let \(S\) be an independent set. If \(x_i\in S\) for some \(i\), then \[S'=(S-\{x_i\})\cup\{a_i,b_i\},\] is independent, and \(d_{G_k}(S')>d_{G_k}(S)\): the size of the set increases by one, while the neighborhood loses the two leaves \(a_i,b_i\) and gains at most the vertex \(x_i\). Hence no critical independent set contains a vertex \(x_i\).
Thus every critical independent set has the form \(Q\cup R\), where \(Q\subseteq A\), \(R\subseteq T\), and \(|R|\le 1\). For such a set, put \[q(Q)=|\{i:Q\cap\{a_i,b_i\}\neq\emptyset\}|.\]
If \(R=\emptyset\), then \[d_{G_k}(Q)=|Q|-q(Q)\le k,\] with equality if and only if \(Q=A\). If \(R=\{r\}\), then \[d_{G_k}(Q\cup R)=|Q|+1-(k+2)\le k-1.\]
Finally, if \(R=\{s\}\) or \(R=\{t\}\), then \[d_{G_k}(Q\cup R)=|Q|+1-(q(Q)+2)=|Q|-q(Q)-1\le k-1.\]
Consequently \(d(G_k)=d_I(G_k)=k\), and the only critical independent set of \(G_k\) is \(A\). In particular, \[\text{ker}(G_k)=A=\{a_i,b_i:1\le i\le k\}.\]
Since \(A\in\text{MaxCritIndep}(G_k)\) and \(N_{G_k}(A)=X\), Theorem 3.1 gives \[L(G_k)=A\cup N_{G_k}(A)=A\cup X=L_k.\]
By Corollary 3.5, \[\mu(G_k)=\mu(kP_3)+\mu(K_3)=k+1.\]
Furthermore, \(d(L_{G_k})=d(kP_3)=k\), and the nontrivial connected components of \(L_{G_k}\) without a perfect matching are precisely the \(k\) copies of \(P_3\). Since \(\text{ker}(G_k)=A\), we have \(|\text{ker}(G_k)|=2k\). Consequently, \[d(L_{G_k})+k=k+k=2k=|\text{ker}(G_k)|.\]
Since \(\alpha(G_k)-\mu(G_k)=(2k+1)-(k+1)=k\), the weaker consequence is sharp as well: \[\alpha(G_k)-\mu(G_k)+k=2k=|\text{ker}(G_k)|.\]
For the graph \(G_4\) in Figure 1, this gives \(\alpha(G_4)=9\), \(\mu(G_4)=5\), \(d(L_{G_4})=4\), and \(|\text{ker}(G_4)|=8\).
Proposition 3.23. Let \(k\) be the number of nontrivial connected components of \(L_G\) without a perfect matching, as in Theorem 3.17. Then \(k\) can be computed in polynomial time.
Proof. By Zhang’s algorithm, a maximum critical independent set \(I\) of \(G\) can be found in polynomial time [35]. Once such a set is known, Larson’s decomposition is obtained as \[L(G)=I\cup N_G(I), \qquad L^c(G)=V(G)-L(G),\] by Theorem 3.1; these sets and the induced graph \(L_G\) can be constructed in polynomial time. The connected components of \(L_G\) are found by a standard graph search. For each nontrivial component \(C\), compute a maximum matching of \(C\) using a polynomial-time matching algorithm, such as Edmonds’ blossom algorithm [6]. The component \(C\) has a perfect matching if and only if \(|V(C)|\) is even and \(\mu(C)=|V(C)|/2\). Counting the nontrivial components failing this test gives \(k\) in polynomial time. \(\square\)
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.