Annihilation, Independence, and Residue:
Sharp Matching Bounds for the Annihilation Gap
and a TxGraffiti Application
July 01, 2026
Abstract
Let \(G\) be a finite simple graph. The annihilation number \(a(G)\) is an efficiently computable upper bound on the independence number \(\alpha(G)\). We develop a sharp matching-number theory for the gap \(a(G)-\alpha(G)\). The strongest general theorem is the exact closed form \[a(G)-\alpha(G)\leq 2\mu(G)+1-\left\lceil \sqrt{6\mu(G)}\right\rceil\qquad(\mu(G)\geq 1),\] and the bound is attained for every prescribed matching number. We also prove sharp matching-dependent bounds for forests, bipartite graphs, and König–Egerváry graphs, with equality constructions, equality certificates, and equality criteria.
Finally, we treat a TxGraffiti output as a machine-conjecture case study. Using annihilating decompositions together with the classical Havel–Hakimi residue inequality \(\operatorname{res}(G)\leq \alpha(G)\), we give an independent proof of the TxGraffiti annihilation-residue inequality \[\alpha(G)\geq \frac{a(G)+\operatorname{res}(G)}{\Delta(G)}\] for every connected graph \(G\) of order at least three, show that both hypotheses are necessary, and compare this proof with a recent Caro–Wei approach. We also refine the Caro–Wei annihilation estimate by an explicit nonnegative slack term, identify its equality cases in degree-sequence form, and combine the refinement with our exact matching-number bound to obtain a combined computable bracket for the independence number and a Gupta–residue bound for the annihilation gap.
Keywords— annihilation number, independence number, matching number, König–Egerváry graph, Havel–Hakimi residue, TxGraffiti
Mathematics Subject Classification (2020)— Primary 05C69; Secondary 05C70, 05C35, 05C85, 68T01.
1 Introduction↩︎
Throughout the paper all graphs are finite, simple, and undirected. Standard graph terminology follows West [1]. For a graph \(G\), let \(V(G)\) and \(E(G)\) denote its vertex and edge sets, and put \(n(G)=|V(G)|\) and \(m(G)=|E(G)|\). We write \(d_G(v)\), or simply \(d(v)\), for the degree of a vertex \(v\), and \(\Delta(G)\) for the maximum degree of \(G\).
An independent set is a set of pairwise non-adjacent vertices. The independence number \(\alpha(G)\) is the maximum cardinality of an independent set. A matching is a set of pairwise disjoint edges, and the matching number \(\mu(G)\) is the maximum cardinality of a matching. We write \(\tau(G)=n(G)-\alpha(G)\) for the vertex cover number; this identity follows because the complement of an independent set is a vertex cover, and conversely. A graph \(G\) is called a König–Egerváry graph if \[\alpha(G)+\mu(G)=n(G).\] This terminology and its matching-cover characterizations go back to the work of Deming, Gavril, and Sterboul [2]–[4]. The classical König–Egerváry theorem for bipartite graphs states that the maximum matching size equals the minimum vertex-cover size; we cite both original papers, by Kőnig and by Egerváry, published in the same 1931 volume of Matematikai és Fizikai Lapok [5], [6]. Consequently, every bipartite graph is König–Egerváry.
Let \[d_1\leq d_2\leq \cdots \leq d_n\] be the degree sequence of \(G\). The annihilation number of \(G\), introduced by Pepper [7], [8], is \[a(G)=\max\left\{k: \sum_{i=1}^k d_i\leq m(G)\right\}.\] Equivalently, an annihilating set is a set \(A\subseteq V(G)\) such that \(\sum_{v\in A}d(v)\leq m(G)\), and \(a(G)\) is the maximum size of an annihilating set. This equivalence follows because, among all \(k\)-vertex subsets, the sum of the \(k\) smallest degrees is the minimum possible degree sum. Thus, an annihilating set need not literally consist of the first \(k\) vertices in a degree ordering; the ordered degree sequence merely computes the largest possible cardinality. Every independent set \(I\) is annihilating, because each edge of \(G\) has at most one endpoint in \(I\), and hence \[\sum_{v\in I}d(v)=e(I,V(G)\setminus I)\leq m(G).\] Consequently, \[\alpha(G)\leq a(G).\] The present paper studies how large the difference \(a(G)-\alpha(G)\) can be under natural structural hypotheses. The work grew out of our earlier arXiv preprint [9], which initiated the annihilation-gap program by proving matching-number bounds for trees, bipartite graphs, and König–Egerváry graphs using annihilating decompositions. Here we revisit that program, sharpen the statements to their correct integral and exact forms, add equality certificates and new extremal families, prove an exact arbitrary-graph matching-number bound, and apply the resulting theory to a TxGraffiti annihilation-residue conjecture.
Automated conjecturing supplies an additional motivation. Fajtlowicz’s Graffiti program generated graph-theoretic inequalities by filtering table-true relations among invariants [10]; see also DeLaViña’s historical account and the modern Dalmatian-heuristic treatment of Larson and Van Cleemput [11], [12]. TxGraffiti continues this line with finite snapshot tables, optimization-based fitting, and Dalmatian-style redundancy filtering [13]. In this terminology, the residue inequality used below is part of the older Graffiti tradition, while the final theorem gives an annihilating-decomposition proof of a TxGraffiti-generated inequality involving \(a(G)\), \(\operatorname{res}(G)\), and \(\Delta(G)\).
The annihilation number has been studied as a computable upper bound for independence and as a companion parameter for domination-type invariants; see, for example, [14]–[23]. Related degree-sequence viewpoints for independence and nullity appear in [24], [25]. The equality problem \(a(G)=\alpha(G)\) has also received sustained attention, including work of Larson and Pepper [26], Levit and Mandrescu [27], [28], Hiller [29], and Rauch and Rautenbach [30].
Our final theorem connects the annihilation number with a second Graffiti-inspired invariant, the Havel–Hakimi residue. Favaron, Mahéo and Saclé [31] introduced and studied the residue and proved that it is bounded above by \(\alpha(G)\); Griggs and Kleitman [32] later gave a short proof. Recently, TxGraffiti generated the conjecture \[\alpha(G)\geq \frac{a(G)+\operatorname{res}(G)}{\Delta(G)}\] for connected graphs of order at least three [13]. During the preparation of this manuscript, Gupta [33] proved the same conjecture independently by a different and stronger route, using a Caro–Wei bound for the annihilation number. We retain the result here because our proof is independent and follows from the annihilating-decomposition and matching-number methods developed in this paper. We also use Gupta’s estimate together with our exact matching-number theorem to obtain a combined computable two-sided bracket for the independence number. A comparison appears in Section 7.
Contribution and novelty calibration↩︎
The first three structural classes below were already central in the earlier Kadrawi–Levit preprint [9]. The present version refines that starting point and adds the general matching theorem, equality-structure information, and the TxGraffiti application. The paper is organized around five main contributions. First, the arbitrary-graph extremal problem with fixed matching number is solved in a closed arithmetic form. Second, König–Egerváry graphs receive a sharp matching-number bound with equality for every prescribed matching number. Third, the forest estimate is sharpened to its correct integral form and is shown to be best possible for every matching number. Fourth, the bipartite non-tree estimate is stated in sharp integer form and is accompanied by equality examples, including a connected six-vertex extremal graph and an infinite connected equality family. Fifth, the TxGraffiti annihilation-residue inequality is proved by an independent annihilating-decomposition argument and presented as a machine-conjecture-to-theorem case study. In the same section, Gupta’s Caro–Wei estimate is sharpened to an exact slack identity, its equality cases are identified in degree-sequence form, and the refinement is combined with our exact matching theorem to give a combined polynomial-time computable bracket for \(\alpha(G)\) and a Gupta–residue upper bound on the same annihilation gap studied throughout the paper. A separate sequel studies the fixed-matching \(K_4\)-free problem by finite matched cores and bounded blow-ups of type graphs.
Proof architecture↩︎
The proofs are organized around one recurring device. Given an annihilating decomposition \(V(G)=A\dot{\cup} B\), the annihilation condition gives \[\sum_{v\in A}d(v)\leq m(G),\] Consequently, Lemma 1 gives the edge-budget inequality \[e(A)\leq e(B).\] The low-degree side \(A\) controls the gap because \[a(G)-\alpha(G)=|A|-\alpha(G) \leq |A|-\alpha(G[A])=\tau(G[A]),\] while the complement \(B\) limits how dense \(G[A]\) can be through \(e(A)\leq e(B)\). Thus, \(A\) supplies the vertex-cover term in the gap, and \(B\) supplies the edge budget that permits \(A\) to be annihilating. The paper uses this device in five increasingly global ways:
for forests, the acyclic structure bounds \(e(A)\) and \(e(B)\) sharply;
for bipartite graphs, the König–Egerváry theorem converts \(|A|-\alpha(G[A])\) into a matching quantity;
for König–Egerváry graphs, the identity \(n=\alpha+\mu\) turns bounds on \(a\) into matching-number estimates;
for arbitrary graphs, the same inequalities reduce the problem to a one-variable optimization in \(c=|B|\), giving the closed form displayed in Theorem A;
for the TxGraffiti inequality, the decomposition gives the auxiliary estimate \[a(G)\leq (\Delta(G)-1)\alpha(G),\] and the residue inequality \(\operatorname{res}(G)\leq\alpha(G)\) completes the proof.
Thus, the TxGraffiti application is not isolated; it is the endpoint of the same annihilating-decomposition method used throughout the paper.
Main theorem overview↩︎
For quick reference, we record the strongest results of the paper.
Theorem A: exact arbitrary-graph matching bound. If \(G\) is any finite simple graph with \(\mu(G)\geq 1\), then \[a(G)-\alpha(G)\leq 2\mu(G)+1-\left\lceil \sqrt{6\mu(G)}\right\rceil.\] This bound is exact for every prescribed positive matching number.
Theorem B: exact König–Egerváry bound. If \(G\) is König–Egerváry, then \[a(G)-\alpha(G)\leq \mu(G)-\left\lceil \frac{\sqrt{8\mu(G)+1}-1}{2}\right\rceil.\] This bound is exact for every prescribed value of \(\mu(G)\); for \(\mu(G)\geq 2\) it is attained by connected non-bipartite König–Egerváry graphs.
Theorem C: sharp forest bound. If \(F\) is a forest with at least one edge, then \[a(F)-\alpha(F)\leq \left\lfloor \frac{\mu(F)-1}{2}\right\rfloor,\] and equality is attained by a tree for every prescribed positive matching number.
Theorem D: sharp bipartite bound, sharp on non-trees. If \(G\) is bipartite, then \[a(G)-\alpha(G)\leq \left\lfloor 2+\mu(G)-2\sqrt{1+\mu(G)}\right\rfloor.\] Equivalently, \[a(G)-\alpha(G)\leq 2+\mu(G)-\left\lceil 2\sqrt{1+\mu(G)}\right\rceil.\] These two forms are the same because \(2+\mu(G)\) is an integer. The equality mechanism for the non-forest case is certified structurally; equality occurs already on six vertices among connected bipartite non-trees, and an infinite connected equality family is given.
Theorem E: TxGraffiti annihilation-residue inequality. If \(G\) is connected and \(n(G)\geq 3\), then \[\alpha(G)\geq \frac{a(G)+\operatorname{res}(G)}{\Delta(G)}.\] Both hypotheses are necessary.
Dependency map and boundary checks↩︎
The main proofs use the following dependency chain. This table is included to make the logical structure easy to audit.
| Input | Used for |
|---|---|
| Sorted-degree definition of \(a(G)\) and annihilating sets | The basic decomposition \(V(G)=A\dot{\cup} B\) and the edge-budget inequality \(e(A)\le e(B)\). |
| Lemma 1 | Forest, bipartite, König–Egerváry and general matching bounds. |
| König–Egerváry theorem for bipartite graphs | Forest and bipartite estimates. |
| Lemmas 6 and 7 | Exact arbitrary-graph fixed-matching bound. |
| Brooks’ theorem and \(\operatorname{res}(G)\le\alpha(G)\) | TxGraffiti application. |
The following small graphs are the boundary tests that the statements must pass.
| Graph | Role in the paper |
|---|---|
| \(K_1\) | Shows why the real-valued forest theorem must exclude edgeless forests. |
| \(K_2\) | Shows the hypothesis \(n(G)\ge3\) is necessary in the TxGraffiti theorem. |
| \(P_3\) | Equality witness for the TxGraffiti theorem. |
| \(C_3\) | Small non-bipartite equality witness in the TxGraffiti theorem and the base odd-cycle case in Lemma 8. |
| \(C_3\cup K_2\) | Shows connectedness is necessary in the TxGraffiti theorem. |
| \(K_4\) | Small sharp witness for both the general matching bound at \(\mu=2\) and the TxGraffiti theorem. |
Sharpness guide↩︎
The following table records the main sharpness and equality witnesses used later. It is intended as a quick map for the reader; the constructions and proofs appear in the relevant sections. In the Bound column, \(\Gamma(\mu)\), \(s(\mu)\) and \(f_{\mathrm{bip}}(\mu)\) denote the expressions displayed in the theorem overview above.
| Result | Bound | Sharpness or equality witnesses |
|---|---|---|
| General graphs | \(a-\alpha\leq \Gamma(\mu)\) | Exact for every \(\mu\) by the clique-budget construction in Theorem [thm:general95exact]; Proposition [prop:general95location] gives necessary equality structure. |
| König–Egerváry graphs | \(a-\alpha\leq \mu-s(\mu)\) | Exact for every \(\mu\); for \(\mu\geq2\) equality occurs in connected non-bipartite König–Egerváry graphs. |
| Forests | \(a-\alpha\leq \lfloor(\mu-1)/2\rfloor\) | The trees \(T_s\) attain equality for every positive \(s=\mu\). |
| Bipartite graphs | \(a-\alpha\leq f_{\mathrm{bip}}(\mu)\) | The bound holds for all bipartite graphs and is sharp on connected bipartite non-trees; equality occurs on the six-vertex graph with edges \(02,03,04,12,13,35\) and on the family \(H_r\). |
| TxGraffiti application | \(\alpha\geq(a+\res)/\Delta\) | Equality occurs for \(P_3,C_3,C_4,K_4\); \(K_2\) and \(C_3\cup K_2\) show that the hypotheses are necessary. |
2 Preliminaries↩︎
For \(X\subseteq V(G)\), write \(G[X]\) for the subgraph induced by \(X\), and write \(e(X)=m(G[X])\). If \(X,Y\subseteq V(G)\) are disjoint, write \(e(X,Y)\) for the number of edges with one endpoint in \(X\) and one endpoint in \(Y\).
Definition 1. An annihilating decomposition* of a graph \(G\) is a partition \(\langle A,B\rangle\) of \(V(G)\) such that \(A\) is a maximum annihilating set and \(B=V(G)\setminus A\). Thus, \(|A|=a(G)\) and \(|B|=n(G)-a(G)\).*
Lemma 1. If \(\langle A,B\rangle\) is an annihilating decomposition of \(G\), then \[e(A)\leq e(B).\]
Proof. Since \(A\) is annihilating, \(\sum_{v\in A}d(v)\leq m(G)\). Hence \[\sum_{v\in B}d(v)=2m(G)-\sum_{v\in A}d(v)\geq m(G),\] so \(\sum_{v\in A}d(v)\leq \sum_{v\in B}d(v)\). But \[\sum_{v\in A}d(v)=2e(A)+e(A,B),\qquad \sum_{v\in B}d(v)=2e(B)+e(A,B).\] Cancelling \(e(A,B)\) gives \(e(A)\leq e(B)\). ◻
Lemma 2. Let \(G\) be bipartite, and let \(\langle A,B\rangle\) be an annihilating decomposition of \(G\). Then \[a(G)-\alpha(G)\leq e(A).\]
Proof. The graph \(G[A]\) is bipartite. Hence, by the König–Egerváry theorem for bipartite graphs [1], [5], [6], \[|A|=\alpha(G[A])+\mu(G[A]).\] Since \(\alpha(G)\geq \alpha(G[A])\) and \(\mu(G[A])\leq e(A)\), we obtain \[a(G)-\alpha(G)=|A|-\alpha(G) \leq |A|-\alpha(G[A]) =\mu(G[A]) \leq e(A).\] ◻
Lemma 3. If \(G\) is König–Egerváry, then \(\mu(G)\leq \alpha(G)\).
Proof. Since every matching has at most \(n(G)/2\) edges and \(\alpha(G)=n(G)-\mu(G)\), we have \[\mu(G)\leq \frac{n(G)}{2}\leq n(G)-\mu(G)=\alpha(G).\] ◻
Lemma 4. Let \(G\) be a graph with at least one edge. Then \(a(G)=n(G)-1\) if and only if all edges of \(G\) are incident with one vertex. Equivalently, \(G\) is a star together with possibly some isolated vertices.
Proof. Let \(d_1\leq \cdots \leq d_n\) be the degree sequence of \(G\). We have \(a(G)=n(G)-1\) if and only if \[\sum_{i=1}^{n-1}d_i\leq m(G).\] Since \(\sum_{i=1}^{n}d_i=2m(G)\), this is equivalent to \(d_n\geq m(G)\). If \(v\) has degree \(d_n\), then \(m(G)=d(v)+m(G-v)\), so \(d_n\geq m(G)\) forces \(m(G-v)=0\). Thus, every edge is incident with \(v\). The converse is immediate from the degree sequence of a star plus isolated vertices. ◻
3 Forests and trees↩︎
The edgeless forest is an exceptional boundary case for a matching-number formulation: if \(F\) is edgeless, then \(a(F)=\alpha(F)=n(F)\) and \(\mu(F)=0\). In particular, the one-vertex tree would make the real-valued right-hand side equal to \(-1/2\). Therefore, the correct statement starts with forests having at least one edge.
Theorem 1. If \(F\) is a forest with at least one edge, then \[a(F)-\alpha(F)\leq \frac{\mu(F)-1}{2}.\] Consequently, \[a(F)-\alpha(F)\leq \left\lfloor \frac{\mu(F)-1}{2}\right\rfloor.\]
Proof. Let \(\langle A,B\rangle\) be an annihilating decomposition of \(F\). Since \(F\) has at least one edge, \(a(F)<n(F)\), and hence, \(B\neq\emptyset\). By Lemmas 1 and 2, \[a(F)-\alpha(F)\leq e(A)\leq e(B).\] The graph \(F[B]\) is a forest on the nonempty vertex set \(B\), so \(e(B)\leq |B|-1\). Therefore, \[a(F)-\alpha(F)\leq |B|-1=n(F)-a(F)-1.\] Since every forest is bipartite, the König–Egerváry theorem gives \(n(F)=\alpha(F)+\mu(F)\). Thus \[a(F)-\alpha(F) \leq \alpha(F)+\mu(F)-a(F)-1,\] and hence \[2(a(F)-\alpha(F))\leq \mu(F)-1.\] This proves the asserted inequality. The floor version follows because the left-hand side is an integer. ◻
Proposition 2 (Forest equality certificate). Let \(F\) be a forest with at least one edge, let \(\langle A,B\rangle\) be an annihilating decomposition, and put \(x=a(F)-\alpha(F)\). If equality holds in the real-valued bound \[x=\frac{\mu(F)-1}{2},\] then \(\mu(F)\) is odd and all inequalities in the proof of Theorem 1 are tight. In particular, \[x=e(A)=e(B)=|B|-1,\] \(F[B]\) is a tree, and \(F[A]\) is a matching of size \(x\) together with isolated vertices.
Proof. The proof of Theorem 1 gives \[x\leq e(A)\leq e(B)\leq |B|-1\] and, since \(F\) is König–Egerváry, \[|B|=n(F)-a(F)=\mu(F)-x.\] Thus, \(x\leq \mu(F)-x-1\). Equality in \(x=(\mu(F)-1)/2\) forces equality throughout the displayed chain. Hence, \(e(B)=|B|-1\), so \(F[B]\) is a tree. Equality in Lemma 2 gives \(|A|-\alpha(F[A])=\mu(F[A])=e(A)\); hence, every edge of \(F[A]\) is a component of a matching, and \(F[A]\) is a matching plus isolated vertices. ◻
Remark 3. Proposition 2 characterizes equality in the real-valued estimate \(a(F)-\alpha(F)\le (\mu(F)-1)/2\). When \(\mu(F)\) is even, equality in the integral floor bound is a separate sharpness question; Proposition 4 supplies the extremal trees for every positive value of \(\mu(F)\).
Proposition 4. For every positive integer \(s\), there is a tree \(T_s\) with \(\mu(T_s)=s\) such that \[a(T_s)-\alpha(T_s)=\left\lfloor \frac{s-1}{2}\right\rfloor.\] Thus, the integral forest/tree bound is sharp for every prescribed positive matching number. The real-valued bound itself is attained exactly by this family when \(s\) is odd.
Proof. For \(s=1\), take \(T_1=K_2\). Now let \(s\geq 2\). Let \(T_s\) be the spider with one arm of length \(1\) and \(s-1\) arms of length \(2\): it has a root \(r\), one leaf adjacent directly to \(r\), and paths \(r u_i w_i\) for \(1\leq i\leq s-1\).
The \(s-1\) vertices \(w_i\) together with the direct leaf form an independent set of size \(s\), and matching each \(u_i\) to \(w_i\) together with matching \(r\) to the direct leaf gives a matching of size \(s\). Since \(T_s\) is bipartite, it is König–Egerváry, and hence, \(\alpha(T_s)=\mu(T_s)=s\).
The degree sequence consists of \(s\) vertices of degree \(1\), \(s-1\) vertices of degree \(2\), and one root of degree \(s\). Also \(m(T_s)=2s-1\). After all \(s\) leaves are selected, the remaining degree budget is \(s-1\), so precisely \(\left\lfloor (s-1)/2\right\rfloor\) vertices of degree \(2\) can be added to a maximum annihilating set. Therefore, \[a(T_s)=s+\left\lfloor \frac{s-1}{2}\right\rfloor,\] and the claimed equality follows. ◻
Corollary 1. If \(F\) is a forest with at least one edge, then \[a(F)\leq \frac{3\alpha(F)-1}{2}.\]
Proof. By Theorem 1 and Lemma 3, \[a(F)-\alpha(F)\leq \frac{\mu(F)-1}{2}\leq \frac{\alpha(F)-1}{2}.\] Rearranging gives the desired inequality. ◻
4 Bipartite graphs↩︎
The bound in this section holds for every bipartite graph. The non-tree hypothesis enters only in the sharpness discussion, where equality is realized by connected bipartite non-trees.
Theorem 5. If \(G\) is bipartite, then \[a(G)-\alpha(G)\leq 2+\mu(G)-2\sqrt{1+\mu(G)}.\] Equivalently, since \(a(G)-\alpha(G)\) is an integer, \[a(G)-\alpha(G)\leq \left\lfloor 2+\mu(G)-2\sqrt{1+\mu(G)}\right\rfloor.\] The same integer bound may also be written in the ceiling form \[a(G)-\alpha(G)\leq 2+\mu(G)-\left\lceil 2\sqrt{1+\mu(G)}\right\rceil.\] The equivalence of the two forms uses that \(2+\mu(G)\) is an integer.
Proof. Let \(\langle A,B\rangle\) be an annihilating decomposition of \(G\), and put \[x=a(G)-\alpha(G).\] By Lemmas 1 and 2, \[x\leq e(A)\leq e(B).\] Since \(G[B]\) is bipartite on \(|B|\) vertices, \[e(B)\leq \frac{|B|^2}{4}.\] Also \(G\) is König–Egerváry, so \(n(G)=\alpha(G)+\mu(G)\), and hence \[|B|=n(G)-a(G)=\mu(G)-x.\] Thus \[x\leq \frac{(\mu(G)-x)^2}{4}.\] This is equivalent to \[x^2-(2\mu(G)+4)x+\mu(G)^2\geq 0.\] The two roots of the corresponding quadratic are \[2+\mu(G)\pm 2\sqrt{1+ \mu(G)}.\] Since \(x\leq \mu(G)\) for König–Egerváry graphs, \(x\) cannot lie above the larger root. Therefore, \[x\leq 2+ \mu(G)-2\sqrt{1+ \mu(G)},\] as required. ◻
Proposition 6 (Bipartite equality certificate). Let \(G\) be a bipartite graph, let \(\langle A,B\rangle\) be an annihilating decomposition, and put \(\mu=\mu(G)\) and \(x=a(G)-\alpha(G)\). If equality holds in the real-valued inequality of Theorem 5, then \(1+\mu\) is a square. Writing \(q=\sqrt{1+\mu}\), one has \[\mu=q^2-1, \qquad x=(q-1)^2, \qquad |B|=2(q-1).\] Moreover, \[e(A)=e(B)=x,\] \(G[B]\) is the complete bipartite graph \(K_{q-1,q-1}\), \(G[A]\) is a matching of size \(x\) together with isolated vertices, and \[\alpha(G)=\alpha(G[A]).\] Conversely, if a bipartite graph has an annihilating decomposition satisfying these displayed conditions for some integer \(q\geq 2\), then it attains equality in the real-valued inequality of Theorem 5.
Proof. The proof of Theorem 5 gives \[x\leq e(A)\leq e(B)\leq \frac{|B|^2}{4}, \qquad |B|=\mu-x.\] Equality in the final bound is equivalent to equality in \[x\leq \frac{(\mu-x)^2}{4}.\] Thus, \(x=2+\mu-2\sqrt{1+\mu}\). Since \(x\) is an integer, \(q=\sqrt{1+\mu}\) is an integer. Hence \[\mu=q^2-1,\] \[x=2+(q^2-1)-2q=(q-1)^2,\] and \[|B|=\mu-x=(q^2-1)-(q-1)^2=2(q-1).\] Equality also forces \[x=e(A)=e(B)=\frac{|B|^2}{4}.\] The last equality is the extremal equality case for bipartite graphs, so \(G[B]\) is \(K_{q-1,q-1}\). Equality in Lemma 2 forces \(\alpha(G)=\alpha(G[A])\) and \(\mu(G[A])=e(A)\); hence, the edges of \(G[A]\) are pairwise disjoint. The converse follows by reversing the same chain of equalities. ◻
Theorem 7 (Connected bipartite real-equality template). Let \(G\) be a connected bipartite graph. Then \(G\) attains equality in the real-valued inequality of Theorem 5 if and only if there is an integer \(q\geq2\) and a partition \(V(G)=A\dot{\cup} B\) with the following properties. First, \(B=B_1\dot{\cup} B_2\), where \(|B_1|=|B_2|=q-1\), and \[G[B]\cong K_{q-1,q-1}\] with partite classes \(B_1\) and \(B_2\). Second, \(G[A]\) is a matching of \((q-1)^2\) edges together with isolated vertices. Third, \(A\) is a maximum annihilating set of \(G\). Fourth, \[\alpha(G)=\alpha(G[A]).\] Finally, the resulting graph is connected.
Equivalently, the fourth condition may be replaced by the following explicit cross-edge condition: for every set \(S\subseteq B_i\), \(i\in\{1,2\}\), \[|S|+\alpha\bigl(G[A\setminus N_G(S)]\bigr)\leq \alpha(G[A]).\] For every graph satisfying these conditions one has \[\mu(G)=q^2-1, \qquad a(G)-\alpha(G)=(q-1)^2.\]
Proof. Suppose first that \(G\) is connected and attains equality. Proposition 6 applied to an annihilating decomposition \(\langle A,B\rangle\) gives an integer \(q\geq2\) such that \(G[B]\cong K_{q-1,q-1}\), \(G[A]\) is a matching of \((q-1)^2\) edges together with isolated vertices, \(A\) is maximum annihilating, and \(\alpha(G)=\alpha(G[A])\). The graph is connected by hypothesis.
It remains only to justify the stated cross-edge reformulation. Since \(G[B]\) is complete bipartite, every independent set that meets \(B\) meets at most one of \(B_1\) and \(B_2\). If its intersection with \(B_i\) is \(S\), then its remaining vertices lie in \(A\setminus N_G(S)\), and hence its size is at most \[|S|+\alpha\bigl(G[A\setminus N_G(S)]\bigr).\] Thus no independent set using vertices of \(B\) is larger than \(\alpha(G[A])\) precisely when the displayed inequality holds for all such \(S\). Independent sets contained in \(A\) are already bounded by \(\alpha(G[A])\).
Conversely, suppose that a connected bipartite graph has such a partition. Since \(A\) is a maximum annihilating set, \(a(G)=|A|\). Since \(G[A]\) is a matching of \((q-1)^2\) edges together with isolated vertices, \[|A|-\alpha(G[A])=(q-1)^2.\] The cross-edge condition gives \(\alpha(G)=\alpha(G[A])\). Therefore \[a(G)-\alpha(G)=|A|-\alpha(G[A])=(q-1)^2.\] Because \(G\) is bipartite, it is König–Egerváry, and so \[\mu(G)=n(G)-\alpha(G)=|B|+|A|-\alpha(G[A])=2(q-1)+(q-1)^2=q^2-1.\] Hence \[2+\mu(G)-2q=2+(q^2-1)-2q=(q-1)^2,\] and equality in Theorem 5 follows. ◻
Remark 8. Theorem 7 is a structural template for the connected bipartite real-equality cases. The remaining freedom is exactly the freedom to add bipartition-preserving cross-edges between the matching-plus-isolates side \(A\) and the balanced complete bipartite side \(B\), subject to the maximum-annihilating condition, the independent-set condition displayed in the theorem, and connectedness. Thus the theorem is not merely a list of examples, but neither does it enumerate every cross-edge pattern separately.
Proposition 9. There is a connected bipartite non-tree on six vertices attaining equality in Theorem 5. Moreover, six is the smallest possible order of a connected bipartite non-tree attaining equality.
Proof. Let \(G\) have vertex set \(\{0,1,2,3,4,5\}\) and edge set \[\{02,03,04,12,13,35\}.\] This graph is connected and bipartite, with bipartition \[\{0,1,5\}\cup \{2,3,4\}.\] It is not a tree, since \(0,2,1,3,0\) is a cycle. Its degree sequence is \[1,1,2,2,3,3,\] and \(m(G)=6\). Hence, \(a(G)=4\). The edges \(04,12,35\) form a perfect matching, so \(\mu(G)=3\), and since \(G\) is bipartite, \(\alpha(G)=n(G)-\mu(G)=3\). Therefore, \[a(G)-\alpha(G)=1.\] On the other hand, \[2+ \mu(G)-2\sqrt{1+ \mu(G)}=2+3-2\sqrt4=1.\] Thus, equality holds.
For minimality, let \(H\) be a connected bipartite non-tree attaining equality. Then \(H\) contains an even cycle, so \(\mu(H)\geq 2\). Equality forces \(2+ \mu(H)-2\sqrt{1+ \mu(H)}\) to be an integer, and hence, \(1+ \mu(H)\) must be a square. If \(n(H)\leq 5\), then \(\mu(H)\leq 2\), and therefore, \(\mu(H)=2\); but then \(1+\mu(H)=3\) is not a square. Hence, no such graph has fewer than six vertices. ◻
Proposition 10. There is an infinite family of connected bipartite non-trees attaining equality in Theorem 5.
Proof. Fix an integer \(r\geq 2\). Start with a complete bipartite graph \(K_{r,r}\) with core bipartition \(X\cup Y\). Attach one pendant leaf to every vertex of \(X\cup Y\). Next add vertices \(b_1,\ldots,b_{r^2}\); join each \(b_i\) to a fixed vertex of \(X\), and attach one pendant leaf \(b_i'\) to \(b_i\). This gives a connected bipartite graph \(H_r\). This family is not obtained by disjoint unions of the six-vertex graph; the complete bipartite core keeps the graph connected. Since \(r\geq 2\), the core \(K_{r,r}\) contains a cycle, so \(H_r\) is not a tree.
The graph has \[n(H_r)=2r^2+4r\] vertices. There is a perfect matching: match every core vertex to its pendant leaf, and match every \(b_i\) to \(b_i'\). Thus \[\mu(H_r)=\frac{n(H_r)}{2}=r^2+2r.\] Because \(H_r\) is bipartite, it is König–Egerváry, and so \[\alpha(H_r)=n(H_r)-\mu(H_r)=r^2+2r.\]
The number of edges is \[m(H_r)=r^2+2r+r^2+r^2=3r^2+2r,\] where the four terms count respectively the edges of \(K_{r,r}\), the pendant edges at the core vertices, the edges joining the \(b_i\) to the core, and the pendant edges \(b_ib_i'\). There are \(r^2+2r\) leaves of degree one and \(r^2\) vertices \(b_i\) of degree two. The sum of their degrees is \[(r^2+2r)+2r^2=3r^2+2r=m(H_r).\] All remaining vertices have degree at least \(r+1\geq 3\), so \[a(H_r)=2r^2+2r.\] Consequently \[a(H_r)-\alpha(H_r)=r^2.\] Since \[\mu(H_r)=r^2+2r=(r+1)^2-1,\] we also have \[2+ \mu(H_r)-2\sqrt{1+ \mu(H_r)} =2+(r+1)^2-1-2(r+1)=r^2.\] Thus, equality holds for every \(r\geq 2\). ◻
Corollary 2. If \(G\) is bipartite, then \[a(G)\leq 2+2\alpha(G)-2\sqrt{1+ \alpha(G)}.\]
Proof. The function \(f(t)=2+t-2\sqrt{1+t}\) is increasing for \(t\geq 0\). By Lemma 3, \(\mu(G)\leq \alpha(G)\). Therefore, Theorem 5 gives \[a(G)-\alpha(G)\leq f(\mu(G))\leq f(\alpha(G)) =2+\alpha(G)-2\sqrt{1+\alpha(G)}.\] Adding \(\alpha(G)\) to both sides gives the claimed inequality. ◻
5 König–Egerváry graphs↩︎
König–Egerváry graphs and their equivalent matching-cover formulations have a substantial structural and algorithmic literature. The foundational characterization and recognition sources include Deming, Gavril, and Sterboul [2]–[4]. Subsequent work has developed the structure of maximum stable sets, cores and coronas, set-and-collection lemmas for families of maximum stable sets, stability under edge operations, and critical edges; see, for example, [34]–[38]. Further work treats common maximum-matching characterizations, critical independent sets, maximum matchings, additional characterizations, deletion-preserving versions of the König–Egerváry property, and \(1\)-König–Egerváry graphs [39]–[44]. The following theorem gives a stronger König–Egerváry estimate than the elementary non-bipartite bound \(a(G)-\alpha(G)\leq \mu(G)-2\).
Theorem 11. Let \(G\) be a König–Egerváry graph, and define \[s(\mu)=\left\lceil \frac{\sqrt{8\mu+1}-1}{2}\right\rceil.\] Then \[a(G)-\alpha(G)\leq \mu(G)-s(\mu(G)).\]
Proof. Let \(\langle A,B\rangle\) be an annihilating decomposition of \(G\), and put \[r=|B|=n(G)-a(G).\] By Lemma 1, \(e(A)\leq e(B)\). Since \(|B|=r\), \[e(B)\leq \binom{r}{2}.\] Let \(M\) be a maximum matching. At most \(r\) edges of \(M\) are incident with vertices of \(B\). Every remaining edge of \(M\) lies in \(G[A]\), so the number of remaining edges is at most \(e(A)\). Therefore, \[\mu(G)=|M|\leq r+e(A)\leq r+e(B)\leq r+\binom{r}{2}=\frac{r(r+1)}{2}.\] Hence \[r\geq \left\lceil \frac{\sqrt{8\mu(G)+1}-1}{2}\right\rceil=s(\mu(G)).\] Since \(G\) is König–Egerváry, \[a(G)-\alpha(G)=n(G)-r-\alpha(G)=\mu(G)-r.\] Combining the last two displays gives the result. ◻
Theorem 12 (Sharpness of the König–Egerváry bound). For \(\mu=1\) there is a connected König–Egerváry graph attaining equality in Theorem 11. For every \(\mu\geq 2\), there is a connected non-bipartite König–Egerváry graph \(G\) with \(\mu(G)=\mu\) and \[a(G)-\alpha(G) = \mu- \left\lceil \frac{\sqrt{8\mu+1}-1}{2}\right\rceil.\] Thus, Theorem 11 is best possible for every prescribed matching number.
Proof. For \(\mu=1\), take \(K_2\). For \(\mu=2\), take a triangle with one pendant leaf attached to one triangle vertex. This graph has \(\alpha=\mu=2\) and \(a=2\), so equality holds. For \(\mu=3\), take a triangle and attach one pendant leaf to each triangle vertex. Then \(\alpha=\mu=3\), the degree sequence is \(1,1,1,3,3,3\), and \(m=6\), so \(a=4\) and \(a-\alpha=1\), which is the asserted value.
Now let \(\mu\geq 4\), and put \[r=\left\lceil \frac{\sqrt{8\mu+1}-1}{2}\right\rceil, \qquad t=\mu-r.\] Then \(r\geq 3\). By definition, \(r\) is the least integer satisfying \[\mu\leq \binom{r+1}{2}.\] Thus \[\binom r2<\mu\leq \binom{r+1}{2}.\] Equivalently, \[t\leq \binom r2, \qquad r+t>\binom r2.\] Construct \(G\) as follows. Start with a clique \(B=K_r\) on vertices \(b_1,\ldots,b_r\). Add pendant vertices \(p_1,\ldots,p_r\), where \(p_i\) is adjacent only to \(b_i\). Finally, add \(t\) disjoint edges \(u_jv_j\), \(1\leq j\leq t\), and join every \(u_j\) to \(b_1\).
The graph is connected and non-bipartite. It has \(2r+2t=2\mu\) vertices and has a perfect matching consisting of the edges \(b_ip_i\) and \(u_jv_j\), so \(\mu(G)=\mu\). Since \(\alpha(G)+\mu(G)\leq n(G)=2\mu\) and the set \[\{p_1,\ldots,p_r\}\cup \{v_1,\ldots,v_t\}\] is independent of size \(r+t=\mu\), we have \(\alpha(G)=\mu\); hence, \(G\) is König–Egerváry.
The number of edges is \[m(G)=\binom r2+r+2t.\] There are \(r+t\) vertices of degree \(1\), namely the \(p_i\) and the \(v_j\), and there are \(t\) vertices \(u_j\) of degree \(2\). The sum of the degrees of these \(r+2t\) vertices is \[r+t+2t=r+3t.\] Since \(t\leq \binom r2\), this sum is at most \(m(G)\). Adding any clique vertex increases the sum by at least \(r\), and this would exceed \(m(G)\) because \(r+t>\binom r2\). Hence \[a(G)=r+2t.\] Therefore, \[a(G)-\alpha(G)=(r+2t)-(r+t)=t=\mu-r,\] which is the claimed equality. ◻
The equality examples in Theorem 12 attain the new exact bound of Theorem 11. The older estimate \(a(G)-\alpha(G)\leq \mu(G)-2\) for non-bipartite König–Egerváry graphs is weaker once \(\mu(G)\geq4\), because then \(s(\mu(G))\geq3\).
Corollary 3. If \(G\) is a non-bipartite König–Egerváry graph, then \[a(G)-\alpha(G)\leq \mu(G)-2.\] Moreover, if \(\mu(G)\geq 4\), then \[a(G)-\alpha(G)\leq \mu(G)-3.\]
Proof. Since \(G\) is non-bipartite, it cannot have an independent set of size \(n(G)-1\); otherwise all edges would be incident with the one vertex outside such a set, making \(G\) bipartite. Thus, \(\alpha(G)\leq n(G)-2\). Because \(G\) is König–Egerváry, \(\mu(G)=n(G)-\alpha(G)\geq 2\), and hence, \(s(\mu(G))\geq 2\). This gives the first inequality from Theorem 11. If \(\mu(G)\geq 4\), then \(s(\mu(G))\geq 3\), giving the second inequality. ◻
Remark 13. Lemma 4 gives another quick proof of the first inequality in Corollary 3. A non-bipartite graph cannot be a star plus isolated vertices, so \(a(G)\leq n(G)-2\). Since \(G\) is König–Egerváry, \(n(G)=\alpha(G)+\mu(G)\), and hence, \(a(G)-\alpha(G)\leq \mu(G)-2\).
Proposition 14. The bound \(a(G)-\alpha(G)\leq \mu(G)-2\) for non-bipartite König–Egerváry graphs is attained for \(\mu=2\) and for \(\mu=3\). For \(\mu\geq 4\), equality in this bound is impossible.
Proof. For \(\mu=2\), take a triangle with one pendant leaf attached to one triangle vertex. Its degree sequence is \(1,2,2,3\), and \(m=4\), so \(a=2\). Also \(\alpha=2\) and \(\mu=2\), whence \(a-\alpha=0=\mu-2\).
For \(\mu=3\), fix \(k\geq 1\) and take a triangle with vertices \(x,y,z\). Attach \(k\) pendant leaves to \(x\), attach \(k\) pendant leaves to \(y\), and attach one pendant leaf to \(z\). The graph has \(2k+4\) vertices and is König–Egerváry with \(\alpha=2k+1\) and \(\mu=3\). Its degree sequence is \[\underbrace{1,\ldots,1}_{2k+1},\;3,\;k+2,\;k+2,\] and \(m=2k+4\). Hence, \(a=2k+2\), and so \[a-\alpha=1=\mu-2.\]
Finally, if \(\mu\geq 4\), Corollary 3 gives \(a-\alpha\leq \mu-3\), so equality in \(a-\alpha\leq \mu-2\) is impossible. ◻
Corollary 4. If \(G\) is a non-bipartite König–Egerváry graph, then \[a(G)\leq 2\alpha(G)-2.\] If, in addition, \(\mu(G)\geq 4\), then \[a(G)\leq 2\alpha(G)-3.\]
Proof. By Corollary 3, \(a(G)-\alpha(G)\leq \mu(G)-2\). Lemma 3 gives \(\mu(G)\leq \alpha(G)\), and hence, \(a(G)\leq 2\alpha(G)-2\). If \(\mu(G)\geq4\), then Corollary 3 gives \(a(G)-\alpha(G)\leq \mu(G)-3\), so the same argument yields \(a(G)\leq2\alpha(G)-3\). ◻
6 General graphs with prescribed matching number↩︎
The preceding sections treat special graph classes. For arbitrary graphs the exact extremal function in terms of the matching number alone is larger, but it has a clean closed form. We first keep the proof in its natural optimization form and then evaluate that optimization explicitly.
For an integer \(\mu\geq 0\), define \[\Phi(\mu)= \max_{0\leq c\leq 2\mu} \min\left\{ 2\mu-c, \left\lfloor \frac{\binom c2+\mu-\left\lfloor c/2\right\rfloor}{2}\right\rfloor \right\}.\] Also define \[\Gamma(0)=0, \qquad \Gamma(\mu)=2\mu+1-\left\lceil \sqrt{6\mu}\right\rceil\quad(\mu\geq 1).\]
Lemma 5. For every integer \(\mu\geq 0\), \[\Phi(\mu)=\Gamma(\mu).\]
Proof. The case \(\mu=0\) is immediate, so assume \(\mu\geq 1\). Put \[A(c)=2\mu-c, \qquad B(c)=\left\lfloor \frac{\binom c2+\mu-\left\lfloor c/2\right\rfloor}{2}\right\rfloor.\] The function \(A(c)\) is strictly decreasing, while \(B(c)\) is nondecreasing. Since \(A(c)\) is integral, \[B(c)\geq A(c)\] if and only if \[\binom c2+\mu-\left\lfloor c/2\right\rfloor\geq 2(2\mu-c),\] or equivalently \[\binom c2+2c-\left\lfloor c/2\right\rfloor\geq 3\mu.\] For every integer \(c\geq 0\), \[\binom c2+2c-\left\lfloor c/2\right\rfloor =\left\lfloor \frac{(c+1)^2}{2}\right\rfloor.\] Thus, the least \(c\) for which \(B(c)\geq A(c)\) is \[c_\mu=\left\lceil \sqrt{6\mu}\right\rceil-1.\] For \(c<c_\mu\), the minimum is \(B(c)\), and by the minimality of \(c_\mu\) we have \[B(c)\leq B(c_\mu-1)<A(c_\mu-1)=A(c_\mu)+1.\] Since \(B(c)\) is integral, \(B(c)\leq A(c_\mu)\). For \(c\geq c_\mu\), the minimum is at most \(A(c)\leq A(c_\mu)\). Hence \[\Phi(\mu)=A(c_\mu)=2\mu+1-\left\lceil \sqrt{6\mu}\right\rceil=\Gamma(\mu).\] ◻
Lemma 6. For every graph \(H\), \[2\tau(H)\leq m(H)+\mu(H).\] Equivalently, \[m(H)\geq 2\tau(H)-\mu(H).\]
Proof. Let \(M\) be a maximum matching of \(H\), with \(|M|=\mu(H)\). Since \(M\) is maximal, every edge of \(H\) has at least one endpoint incident with an edge of \(M\). Choose independently and uniformly one endpoint from each edge of \(M\), and let \(S\) be the set of chosen vertices. The set \(S\) covers all edges of \(M\). If an edge outside \(M\) has one endpoint not incident with \(M\), then it is uncovered by \(S\) with probability \(1/2\); if its endpoints lie on two distinct edges of \(M\), then it is uncovered with probability \(1/4\). In all cases, the probability that a non-matching edge is uncovered is at most \(1/2\).
Now add one endpoint of every uncovered non-matching edge to \(S\). The resulting set is a vertex cover. Its expected size is at most \[\mu(H)+\frac{m(H)-\mu(H)}{2} =\frac{m(H)+\mu(H)}{2}.\] Therefore, \(H\) has a vertex cover of size at most \((m(H)+\mu(H))/2\), which is the desired inequality. ◻
Lemma 7. If \(H\) has \(c\) vertices, then \[m(H)-\mu(H)\leq \binom c2-\left\lfloor c/2\right\rfloor.\]
Proof. Add the missing edges of \(H\) one at a time until the complete graph \(K_c\) is obtained. Adding one edge increases the number of edges by \(1\) and increases the matching number by at most \(1\). Thus, the quantity \(m(H)-\mu(H)\) never decreases during this process. Hence \[m(H)-\mu(H) \leq m(K_c)-\mu(K_c) =\binom c2-\left\lfloor c/2\right\rfloor.\] ◻
Theorem 15 (Exact general matching bound). For every finite simple graph \(G\), \[a(G)-\alpha(G)\leq \Gamma(\mu(G)).\] Equivalently, if \(\mu(G)\geq 1\), then \[a(G)-\alpha(G) \leq 2\mu(G)+1-\left\lceil \sqrt{6\mu(G)}\right\rceil.\] Moreover, for every integer \(\mu\geq 0\), there exists a graph \(G\) with \(\mu(G)=\mu\) and \[a(G)-\alpha(G)=\Gamma(\mu).\]
Proof. Let \(\mu=\mu(G)\), let \(\langle A,B\rangle\) be an annihilating decomposition, and put \[x=a(G)-\alpha(G), \qquad c=|B|=n(G)-a(G).\] Since the endpoints of a maximum matching form a vertex cover, \(\tau(G)=n(G)-\alpha(G)\leq 2\mu\). Hence \[x+c=n(G)-\alpha(G)\leq 2\mu,\] and so \[\label{eq:general95first95bound959} x\leq 2\mu-c.\tag{1}\]
Let \(H=G[A]\) and \(J=G[B]\). Since \(\alpha(G)\geq \alpha(H)\), \[x=|A|-\alpha(G)\leq |A|-\alpha(H)=\tau(H).\] By Lemma 6, \[e(A)=m(H)\geq 2\tau(H)-\mu(H)\geq 2x-\mu(H).\] The matchings of \(H\) and \(J\) are vertex-disjoint, and hence \[\mu(H)+\mu(J)\leq \mu.\] Using Lemma 1 and Lemma 7, we get \[\begin{align} 2x &\leq e(A)+\mu(H) \\ &\leq e(B)+\mu-\mu(J) \\ &=\mu+\bigl(e(B)-\mu(J)\bigr) \\ &\leq \mu+\binom c2-\left\lfloor c/2\right\rfloor. \end{align}\] Thus \[\label{eq:general95second95bound959} x\leq \left\lfloor \frac{\binom c2+\mu-\left\lfloor c/2\right\rfloor}{2}\right\rfloor.\tag{2}\] Combining 1 and 2 gives \(x\leq\Phi(\mu)\), and Lemma 5 gives \(x\leq\Gamma(\mu)\).
It remains to prove sharpness. The cases \(\mu=0\) and \(\mu=1\) are realized by an edgeless graph and by \(K_3\), respectively. Assume \(\mu\geq 2\), and set \[c=\left\lceil \sqrt{6\mu}\right\rceil-1, \qquad X=\Gamma(\mu)=2\mu-c, \qquad t=\left\lfloor c/2\right\rfloor, \qquad s=\mu-t.\] The proof of Lemma 5 gives \[X\leq \left\lfloor \frac{\binom c2+s}{2}\right\rfloor,\] and hence \(2X-s\leq \binom c2\). Also \(s\leq X\leq 2s\). Put \[q=X-s, \qquad p=2s-X.\] Then \(p,q\geq 0\). Let \(H\) be the disjoint union of \(q\) triangles and \(p\) copies of \(K_2\). Then \[\tau(H)=X, \qquad \mu(H)=s, \qquad m(H)=2X-s.\] Let \(B\) induce a clique \(K_c\). Since \(m(H)\leq \binom c2\), there are enough edges in \(B\) to make the vertex set of \(H\) annihilating after the joining operation below.
If \(p>0\), choose one of the \(K_2\) components of \(H\) and join every vertex of \(B\) to both of its vertices. If \(p=0\), then \(q>0\); choose one triangle component of \(H\) and join every vertex of \(B\) to all three of its vertices. Let \(G\) be the resulting graph. The chosen component intersects every maximum independent set of \(H\), so adding vertices from \(B\) cannot increase the independence number. Hence \[\alpha(G)=\alpha(H)=|V(H)|-X.\] The matching number is \[\mu(G)=s+\left\lfloor c/2\right\rfloor=\mu.\] Indeed, if \(p>0\), the joined block is obtained from \(K_c\cup K_2\) by adding all edges between \(K_c\) and the chosen \(K_2\); it is the clique \(K_{c+2}\) and has matching number \[\left\lfloor (c+2)/2\right\rfloor=\left\lfloor c/2\right\rfloor+1,\] the same as \(K_c\cup K_2\). If \(p=0\), then \(X=2s\). Since \(X=2\mu-c\) and \(s=\mu-\left\lfloor c/2\right\rfloor\), we get \(c=2\left\lfloor c/2\right\rfloor\), so \(c\) is even. The joined block is then \(K_{c+3}\), whose matching number is \[\left\lfloor (c+3)/2\right\rfloor=c/2+1=\left\lfloor c/2\right\rfloor+1,\] the same as \(K_c\) together with the chosen triangle. All other components of \(H\) are disjoint from the joined block, and hence, the total matching number is \(s+\left\lfloor c/2\right\rfloor=\mu\).
Finally, if \(R\) is the number of cross-edges between \(H\) and \(B\), then the degree sum over \(V(H)\) is \(2m(H)+R\), while \[m(G)=m(H)+\binom c2+R.\] Since \(m(H)\leq\binom c2\), the set \(V(H)\) is annihilating in \(G\). Therefore, \[a(G)-\alpha(G) \geq |V(H)|-(|V(H)|-X)=X=\Gamma(\mu).\] The upper bound already proved forces equality. ◻
Proposition 16 (Location of extremal decompositions). Let \(G\) satisfy equality in Theorem 15, and put \(\mu=\mu(G)\geq3\). Let \(\langle A,B\rangle\) be an annihilating decomposition, set \(c=|B|\), and put \[r=\left\lceil \sqrt{6\mu}\right\rceil.\] Then \[c\in\{r-2,r-1\}.\] Consequently \[n(G)-\alpha(G)=a(G)-\alpha(G)+|B|\in\{2\mu-1,2\mu\}.\] Equivalently, every extremal graph for the general matching bound has matching-cover defect \[2\mu(G)-\tau(G)\in\{0,1\}.\] If \(c=r-1\), then \(\tau(G)=2\mu(G)\), so the endpoints of every maximum matching form a minimum vertex cover. If \(c=r-2\), then \(\tau(G)=2\mu(G)-1\) and the second inequality in the proof of Theorem 15 is tight for this decomposition.
Proof. Let \(x=a(G)-\alpha(G)\). Since equality holds, \[x=\Gamma(\mu)=2\mu+1-r.\] The first bound in the proof of Theorem 15 gives \[x\leq 2\mu-c,\] so \(c\leq r-1\).
We claim that \(c\leq r-3\) is impossible. Since \(\mu\geq3\), we have \(r\geq5\) and \((r-1)^2<6\mu\). Let \[B_\mu(c)=\left\lfloor \frac{\binom c2+\mu-\left\lfloor c/2\right\rfloor}{2}\right\rfloor.\] The function \(B_\mu(c)\) is nondecreasing in \(c\). Hence, if \(c\leq r-3\), then \[B_\mu(c)\leq B_\mu(r-3).\] It is enough to show \(B_\mu(r-3)<\Gamma(\mu)\). Put \[N=\binom{r-3}{2}+\mu-\left\lfloor \frac{r-3}{2}\right\rfloor.\] Since \[\binom{r-3}{2}+2r-2-\left\lfloor \frac{r-3}{2}\right\rfloor \leq \frac{(r-1)^2}{2} <3\mu,\] we get \[N<4\mu+2-2r=2\Gamma(\mu).\] Thus, \(B_\mu(r-3)=\lfloor N/2\rfloor<\Gamma(\mu)\), and hence, \(B_\mu(c)<\Gamma(\mu)\) for all \(c\leq r-3\). This contradicts the second bound in the proof of Theorem 15, which is necessary for \(x=\Gamma(\mu)\). Therefore, \(c\geq r-2\).
Combining \(c\leq r-1\) and \(c\geq r-2\) gives \(c\in\{r-2,r-1\}\). Since \[\tau(G)=n(G)-\alpha(G)=a(G)-\alpha(G)+|B|=x+c,\] we obtain \(\tau(G)=2\mu\) when \(c=r-1\) and \(\tau(G)=2\mu-1\) when \(c=r-2\). In the latter case the first bound gives only \(x\leq\Gamma(\mu)+1\); hence, equality in the overall theorem forces the second bound to be tight. ◻
Proposition 17 (Equality certificates for the general bound). Let \(G\) satisfy equality in Theorem 15, let \(\mu=\mu(G)\), and let \(\langle A,B\rangle\) be an annihilating decomposition. Put \(c=|B|\) and \(x=a(G)-\alpha(G)\). Then \[x=\Gamma(\mu)\] and \[\min\left\{2\mu-c, \left\lfloor \frac{\binom c2+\mu-\left\lfloor c/2\right\rfloor}{2}\right\rfloor\right\}=\Gamma(\mu).\] If the second entry in the minimum is tight for this decomposition, then all of the following equalities hold: \[\alpha(G)=\alpha(G[A]), \qquad 2\tau(G[A])=e(A)+\mu(G[A]),\] \[e(A)=e(B), \qquad \mu(G[A])+\mu(G[B])=\mu(G),\] and \[e(B)-\mu(G[B])=\binom c2-\left\lfloor c/2\right\rfloor.\] Together with Proposition 16, this reduces an isomorphism-level equality classification to the defect-zero and defect-one decompositions for which the proof inequalities are simultaneously sharp.
Proof. The first assertion follows immediately from the proof of Theorem 15. If the second entry is tight, equality must hold in each inequality in the chain \[2x\leq e(A)+\mu(G[A])\leq e(B)+\mu(G)-\mu(G[B]) \leq \mu(G)+\binom c2-\left\lfloor c/2\right\rfloor.\] Unwinding the equalities gives the listed conditions. ◻
Theorem 18 (Matching-cover defect criterion for equality in the exact general bound). Let \(G\) be a finite simple graph and put \(\mu=\mu(G)\). If \(\mu=0\), then equality in Theorem 15 holds exactly for edgeless graphs. If \(\mu=1\), then every graph with matching number one attains equality. If \(\mu=2\), then equality holds exactly when \(a(G)=\alpha(G)+1\).
Assume now that \(\mu\geq3\), and put \[r=\left\lceil \sqrt{6\mu}\right\rceil.\] Then \(G\) attains equality in Theorem 15 if and only if one of the following two mutually exclusive alternatives holds: \[a(G)=n(G)-r+1 \quad\text{and}\quad \tau(G)=2\mu,\] or \[a(G)=n(G)-r+2 \quad\text{and}\quad \tau(G)=2\mu-1.\] Equivalently, if \(\langle A,B\rangle\) is an annihilating decomposition, then equality holds if and only if either \[|B|=r-1 \quad\text{and}\quad \tau(G)=2\mu,\] or \[|B|=r-2 \quad\text{and}\quad \tau(G)=2\mu-1.\] In the second alternative, the second proof inequality in Theorem 15 is tight, and the equalities listed in Proposition 17 hold for the corresponding annihilating decomposition.
Proof. The cases \(\mu=0\) and \(\mu=1\) follow directly from the formula \(\Gamma(0)=0\) and \(\Gamma(1)=0\), together with \(\alpha(G)\leq a(G)\). For \(\mu=2\), the bound gives \(a(G)-\alpha(G)\leq1\), so equality is exactly the condition \(a(G)=\alpha(G)+1\).
Now assume \(\mu\geq3\). Let \(\langle A,B\rangle\) be an annihilating decomposition and put \(c=|B|=n(G)-a(G)\). If equality holds, Proposition 16 gives \[c\in\{r-2,r-1\}\] and \[\tau(G)=a(G)-\alpha(G)+c\in\{2\mu-1,2\mu\}.\] More precisely, \(c=r-1\) gives \(\tau(G)=2\mu\), while \(c=r-2\) gives \(\tau(G)=2\mu-1\). Since \(c=n(G)-a(G)\), these are exactly the two alternatives displayed in the theorem.
Conversely, suppose first that \(a(G)=n(G)-r+1\) and \(\tau(G)=2\mu\). Then \[a(G)-\alpha(G)=a(G)-n(G)+\tau(G)=2\mu-r+1=\Gamma(\mu).\] Similarly, if \(a(G)=n(G)-r+2\) and \(\tau(G)=2\mu-1\), then \[a(G)-\alpha(G)=a(G)-n(G)+\tau(G)=2\mu-r+1=\Gamma(\mu).\] Thus equality holds in Theorem 15. The final statement is precisely the last assertion of Proposition 16 together with Proposition 17. ◻
Remark 19. The extremal construction in Theorem 15 explains why the arbitrary-graph problem differs sharply from the König–Egerváry problem. Low-degree odd components, especially triangles, can contribute two units to the vertex-cover side of the gap while using only one matching edge; a dense clique supplies the edge budget needed for the low-degree part to be annihilating.
7 A TxGraffiti inequality as a machine-conjecture case study↩︎
The Havel–Hakimi residue is one of the classical invariants arising from the Graffiti tradition. We use the following standard comparison theorem.
Theorem 20 (Caro–Wei; Favaron–Mahéo–Saclé; Griggs–Kleitman). For every graph \(G\), \[W(G):=\sum_{v\in V(G)}\frac{1}{d(v)+1}\leq \operatorname{res}(G)\leq \alpha(G).\]
The lower bound \(W(G)\leq\alpha(G)\) is the classical Caro–Wei theorem; see Caro [45] and Wei [46]. The stronger comparison \(W(G)\leq\operatorname{res}(G)\) and the residue bound \(\operatorname{res}(G)\leq\alpha(G)\) are due to Favaron, Mahéo and Saclé [31]; Griggs and Kleitman later gave a short proof of the residue lower bound for independence [32]. Informally, the Havel–Hakimi reductions can be followed inductively so that the zero entries remaining at termination certify an independent set of at least that size. In this paper we use only the displayed standard consequences.
TxGraffiti operates with finite versioned snapshot tables of graph invariants and Boolean predicates. It returns inequalities that are true on the snapshot, but these outputs are conjectures until proved outside the table. In the terminology of [13], the following statement was produced after adding the derived target \(\alpha(G)\Delta(G)\), the product of the independence number and maximum degree, and fitting a multivariate lower-bound template involving \(a(G)\) and \(\operatorname{res}(G)\).
Conjecture 21 (TxGraffiti). If \(G\) is a connected graph with \(n(G)\geq 3\), then \[\alpha(G)\geq \frac{a(G)+\operatorname{res}(G)}{\Delta(G)}.\]
The following table summarizes the proof status of the machine output. TxGraffiti supplies the first line as a table-true conjecture on its snapshot; the remaining lines are the structural ingredients and sharpness checks supplied here.
| TxGraffiti output | \(\displaystyle \alpha(G)\geq \frac{a(G)+\operatorname{res}(G)}{\Delta(G)}\) |
|---|---|
| Hypotheses | \(G\) connected and \(n(G)\geq3\) |
| Main proof ingredients | \(a(G)\leq(\Delta(G)-1)\alpha(G)\) and \(\operatorname{res}(G)\leq\alpha(G)\) |
| Why \(n\geq3\) is needed | \(K_2\) violates the inequality |
| Why connectedness is needed | \(C_3\cup K_2\) violates the inequality |
| Equality witnesses | \(P_3\), \(C_3\), \(C_4\), and \(K_4\) |
The conjecture is not a formal consequence of the two basic inequalities \(\alpha(G)\leq a(G)\) and \(\operatorname{res}(G)\leq\alpha(G)\). The missing ingredient is an upper bound on the annihilation number itself in terms of \(\Delta(G)\) and \(\alpha(G)\). Gupta’s recent proof supplies such a bound through the Caro–Wei sum \(W(G)\), namely \[a(G)\leq \frac{\Delta(G)+1}{2}W(G),\] and combines it with the classical bounds recalled in Theorem 20 [33]. The proof below follows a different route: it first proves the structural estimate \(a(G)\leq(\Delta(G)-1)\alpha(G)\) by annihilating decompositions, Brooks’ theorem, and the forest bound.
Gupta’s estimate is also useful inside the present paper. The proof of his Caro–Wei bound contains more information than the displayed inequality alone. Keeping the nonnegative slack terms gives an exact refinement, which can be combined with our matching-number theorem to produce a combined bracket for the independence number.
For a graph with at least one edge, write the degree sequence as \[d_1\leq d_2\leq\cdots\leq d_n,\] put \(a=a(G)\) and \(\Delta=\Delta(G)\), and define the Caro–Wei sum \[W(G)=\sum_{i=1}^n\frac{1}{d_i+1}.\] Let \[S_H(G)=\sum_{i=1}^{a}d_i\] be the degree sum of the annihilation head. Define the Gupta slack \[\begin{align} \sigma_\Delta(G)=&\frac{\Delta(n-a)-S_H(G)}{2\Delta} \\ &+\sum_{i=1}^{a}\frac{(\Delta-d_i)(\Delta-d_i-1)}{2\Delta(d_i+1)} +\sum_{i=a+1}^{n}\frac{\Delta-d_i}{2(d_i+1)} . \end{align}\] Each summand is nonnegative.
Theorem 22 (Refined Gupta slack identity). Every graph \(G\) with at least one edge satisfies \[a(G)+\sigma_\Delta(G)=\frac{\Delta(G)+1}{2}W(G).\] In particular, \[a(G)\leq \frac{\Delta(G)+1}{2}W(G),\] with the loss from equality measured exactly by \(\sigma_\Delta(G)\).
Proof. Let \(H=\{1,\ldots,a\}\) and \(T=\{a+1,\ldots,n\}\) be the annihilation head and tail in the nondecreasing degree sequence. Since \(a\) is the annihilation number, \[S_H(G)=\sum_{i\in H}d_i\leq m(G).\] Hence \[\sum_{i\in T}d_i=2m(G)-S_H(G)\geq S_H(G),\] and, because each tail degree is at most \(\Delta\), \[S_H(G)\leq \Delta(n-a).\] For every integer \(0\leq k\leq\Delta\), the identity \[\frac{1}{k+1} =\frac{2}{\Delta+1}-\frac{k}{\Delta(\Delta+1)} +\frac{(\Delta-k)(\Delta-k-1)}{\Delta(\Delta+1)(k+1)}\] refines the pointwise inequality used in Gupta’s proof. For tail degrees we also have the exact identity \[\frac{1}{k+1}=\frac{1}{\Delta+1}+\frac{\Delta-k}{(\Delta+1)(k+1)}.\] Summing the first identity over \(H\) and the second over \(T\) gives \[\begin{align} W(G)=&\frac{2a}{\Delta+1}-\frac{S_H(G)}{\Delta(\Delta+1)} +\sum_{i=1}^{a}\frac{(\Delta-d_i)(\Delta-d_i-1)}{\Delta(\Delta+1)(d_i+1)}\\ &+\frac{n-a}{\Delta+1} +\sum_{i=a+1}^{n}\frac{\Delta-d_i}{(\Delta+1)(d_i+1)} . \end{align}\] Multiplying by \((\Delta+1)/2\) and rearranging gives exactly \[\frac{\Delta+1}{2}W(G)=a(G)+\sigma_\Delta(G).\] The inequality follows because \(\sigma_\Delta(G)\geq0\). ◻
Corollary 5 (Equality in Gupta’s Caro–Wei annihilation bound). Let \(G\) be a graph with at least one edge, degree sequence \(d_1\leq\cdots\leq d_n\), maximum degree \(\Delta\), annihilation number \(a=a(G)\), and annihilation-head degree sum \[S_H(G)=\sum_{i=1}^{a}d_i.\] Then equality holds in Gupta’s inequality \[a(G)=\frac{\Delta(G)+1}{2}W(G)\] if and only if all three of the following degree-sequence conditions hold:
\(S_H(G)=\Delta(n-a)\);
every head degree satisfies \(d_i\in\{\Delta-1,\Delta\}\) for \(1\leq i\leq a\);
every tail degree satisfies \(d_i=\Delta\) for \(a+1\leq i\leq n\).
Equivalently, equality holds if and only if \(\sigma_\Delta(G)=0\).
Proof. By Theorem 22, equality in Gupta’s bound is equivalent to \(\sigma_\Delta(G)=0\). Since \(\sigma_\Delta(G)\) is a sum of nonnegative terms, it vanishes precisely when each term vanishes. The first slack term gives \(S_H(G)=\Delta(n-a)\). The head summand \[\frac{(\Delta-d_i)(\Delta-d_i-1)}{2\Delta(d_i+1)}\] vanishes exactly when \(\Delta-d_i\in\{0,1\}\), that is, \(d_i\in\{\Delta,\Delta-1\}\). The tail summand \[\frac{\Delta-d_i}{2(d_i+1)}\] vanishes exactly when \(d_i=\Delta\). These are the three displayed conditions. ◻
Corollary 6 (Combined computable independence bracket). Let \(G\) be a graph with at least one edge. Then \[\max\left\{\operatorname{res}(G),\, W(G),\, a(G)-\Gamma(\mu(G))\right\} \leq \alpha(G)\leq a(G).\] Moreover, \[a(G)=\frac{\Delta(G)+1}{2}W(G)-\sigma_\Delta(G) \leq \frac{\Delta(G)+1}{2}\operatorname{res}(G)-\sigma_\Delta(G).\]
Proof. Theorem 20 gives \(W(G)\leq\operatorname{res}(G)\leq\alpha(G)\). Theorem 15 gives \(a(G)-\alpha(G)\leq\Gamma(\mu(G))\), and hence \(a(G)-\Gamma(\mu(G))\leq\alpha(G)\). Pepper’s annihilation bound gives \(\alpha(G)\leq a(G)\). Theorem 22 gives the displayed identity for \(a(G)\), and Theorem 20 gives \(W(G)\leq\operatorname{res}(G)\). ◻
Corollary 7 (Gupta–residue annihilation-gap bound). Let \(G\) be a graph with at least one edge. Then \[a(G)-\alpha(G) \leq \min\left\{ \Gamma(\mu(G)),\, a(G)-\operatorname{res}(G) \right\}.\] Moreover, writing \(\Delta=\Delta(G)\), \(a=a(G)\), \(R=\operatorname{res}(G)\), \(W=W(G)\), and \(\sigma=\sigma_\Delta(G)\), one has the exact identity \[a(G)-\operatorname{res}(G) = \frac{(\Delta-1)a(G)-2\sigma_\Delta(G)}{\Delta+1} -\bigl(\operatorname{res}(G)-W(G)\bigr).\] Denote this last expression by \(\Theta_{\rm GR}(G)\). Consequently, \[a(G)-\alpha(G) \leq \min\{\Gamma(\mu(G)),\Theta_{\rm GR}(G)\}.\] In particular, any graph attaining equality in the exact matching bound of Theorem 15 must satisfy \[(\Delta(G)+1)\Gamma(\mu(G)) \leq (\Delta(G)-1)a(G)-2\sigma_\Delta(G) -(\Delta(G)+1)\bigl(\operatorname{res}(G)-W(G)\bigr).\]
Proof. The first inequality follows from Theorem 15 and Theorem 20: since \(\alpha(G)\geq\operatorname{res}(G)\), \[a(G)-\alpha(G)\leq a(G)-\operatorname{res}(G),\] while Theorem 15 gives \(a(G)-\alpha(G)\leq\Gamma(\mu(G))\). By Theorem 22, \[a(G)=\frac{\Delta+1}{2}W-\sigma.\] Therefore \[\begin{align} a(G)-\operatorname{res}(G) &=\frac{\Delta+1}{2}W-\sigma-R\\ &=\frac{(\Delta-1)a(G)-2\sigma}{\Delta+1}-(R-W), \end{align}\] where the second equality follows by substituting \(W=2(a+\sigma)/(\Delta+1)\). This proves the displayed Gupta–residue gap bound. If \(a(G)-\alpha(G)=\Gamma(\mu(G))\), then the same bound forces the final displayed necessary condition. ◻
Corollary 8 (Quantitative domination of the TxGraffiti lower bound). If \(G\) has \(\Delta(G)\geq3\), then \[\frac{a(G)+\operatorname{res}(G)}{\Delta(G)}\leq \operatorname{res}(G)\leq\alpha(G).\] More precisely, write \(\Delta=\Delta(G)\), \(R=\operatorname{res}(G)\), \(W=W(G)\), and \(\sigma=\sigma_\Delta(G)\). Then \[R-\frac{a(G)+R}{\Delta} = \frac{(\Delta-3)R}{2\Delta} +\frac{(\Delta+1)(R-W)}{2\Delta} +\frac{\sigma}{\Delta} .\] Consequently, equality in the domination of the TxGraffiti lower bound by \(\operatorname{res}(G)\) occurs if and only if \(\Delta(G)=3\), \(W(G)=\operatorname{res}(G)\), and \(\sigma_\Delta(G)=0\).
Proof. By Theorem 22, \[a(G)=\frac{\Delta+1}{2}W-\sigma.\] Therefore \[\begin{align} R-\frac{a(G)+R}{\Delta} &=\frac{(\Delta-1)R-a(G)}{\Delta}\\ &=\frac{(\Delta-1)R-\frac{\Delta+1}{2}W+\sigma}{\Delta}\\ &=\frac{(\Delta-3)R}{2\Delta} +\frac{(\Delta+1)(R-W)}{2\Delta} +\frac{\sigma}{\Delta}. \end{align}\] The right-hand side is nonnegative for \(\Delta\geq3\), since \(R\geq W\) and \(\sigma\geq0\). This proves the sharpened inequality and the equality condition. ◻
Corollary 9 (Equality in the TxGraffiti inequality). Let \(G\) be connected with \(n(G)\geq3\). If \(\Delta(G)=2\), then equality in Theorem 23 holds if and only if \(\operatorname{res}(G)=\alpha(G)\). If \(\Delta(G)\geq3\), then equality in Theorem 23 holds if and only if \[\Delta(G)=3,\qquad W(G)=\operatorname{res}(G)=\alpha(G),\qquad \sigma_\Delta(G)=0.\]
Proof. If \(\Delta(G)=2\), then \(G\) is a path or a cycle. In both cases \(a(G)=\alpha(G)\), and hence \[\alpha(G)=\frac{a(G)+\operatorname{res}(G)}{2}\] holds if and only if \(\operatorname{res}(G)=\alpha(G)\).
Now assume \(\Delta(G)\geq3\). By Corollary 8, \[\frac{a(G)+\operatorname{res}(G)}{\Delta(G)}\leq \operatorname{res}(G)\leq \alpha(G).\] Thus equality in Theorem 23 holds if and only if both inequalities in this chain are equalities. The first equality is characterized by Corollary 8: it is equivalent to \(\Delta(G)=3\), \(W(G)=\operatorname{res}(G)\), and \(\sigma_\Delta(G)=0\). The second equality is \(\operatorname{res}(G)=\alpha(G)\). This gives exactly the displayed conditions. ◻
Lemma 8. If \(G\) is a connected graph with \(n(G)\geq 3\), then \[a(G)\leq (\Delta(G)-1)\alpha(G).\]
Proof. Write \(n=n(G)\), \(m=m(G)\), \(a=a(G)\), \(\alpha=\alpha(G)\), and \(\Delta=\Delta(G)\). Since \(G\) is connected and \(n\geq3\), we have \(\Delta\geq2\). Let \(\langle A,B\rangle\) be an annihilating decomposition of \(G\). Since \(\sum_{v\in A}d(v)\leq m\), we have \(\sum_{v\in B}d(v)\geq m\). Hence \[m\leq \sum_{v\in B}d(v)\leq \Delta |B|=\Delta(n-a),\] which gives \[\label{eq:a95nmDelta95case} a\leq n-\frac{m}{\Delta}.\tag{3}\]
First suppose that \(G\) is not a tree. Then \(m\geq n\). If \(G\) is neither a complete graph nor an odd cycle, Brooks’ theorem gives \(\chi(G)\leq \Delta\) [47]. A coloring with at most \(\Delta\) color classes has an independent color class of size at least \(n/\Delta\); hence \[\alpha\geq \frac{n}{\Delta}.\] Using 3 , we obtain \[a\leq n-\frac{m}{\Delta} \leq n-\frac{n}{\Delta} =\frac{(\Delta-1)n}{\Delta} \leq (\Delta-1)\alpha.\] If \(G\) is an odd cycle, then \(\Delta=2\) and \(a=\alpha=(n-1)/2\), so the desired inequality holds. If \(G=K_{\Delta+1}\), then \(\alpha=1\) and \[a=\left\lfloor \frac{\Delta+1}{2}\right\rfloor\leq \Delta-1\] for \(\Delta\geq 2\), again giving \(a\leq (\Delta-1)\alpha\).
Now suppose that \(G\) is a tree. If \(\Delta=2\), then \(G\) is a path and \(a=\alpha=\left\lceil n/2\right\rceil\), so the result holds. If \(\Delta\geq 3\), Theorem 1 and Lemma 3 give \[a\leq \alpha+\frac{\mu(G)-1}{2} \leq \alpha+\frac{\alpha-1}{2} =\frac{3\alpha-1}{2} \leq 2\alpha \leq (\Delta-1)\alpha.\] This completes the proof. ◻
Theorem 23 (An annihilating-decomposition proof of the TxGraffiti inequality). If \(G\) is a connected graph with \(n(G)\geq 3\), then \[\alpha(G)\geq \frac{a(G)+\operatorname{res}(G)}{\Delta(G)}.\]
Proof. By Lemma 8, \[a(G)\leq (\Delta(G)-1)\alpha(G).\] By Theorem 20, \[\operatorname{res}(G)\leq \alpha(G).\] Adding the two inequalities gives \[a(G)+\operatorname{res}(G) \leq (\Delta(G)-1)\alpha(G)+\alpha(G) =\Delta(G)\alpha(G).\] Since \(G\) is connected and \(n(G)\geq 3\), we have \(\Delta(G)\geq 2\). Dividing by \(\Delta(G)\) proves the theorem. ◻
Proposition 24 (Necessity of the TxGraffiti hypotheses). Both hypotheses in Theorem 23 are necessary.
Proof. The order assumption cannot be removed. For \(K_2\), \[\alpha(K_2)=1, \qquad a(K_2)=1, \qquad \operatorname{res}(K_2)=1, \qquad \Delta(K_2)=1.\] Thus \[\frac{a(K_2)+\operatorname{res}(K_2)}{\Delta(K_2)}=2>1=\alpha(K_2).\]
Connectedness cannot be removed either. Let \(G=C_3\cup K_2\). Then \[\alpha(G)=2, \qquad a(G)=3, \qquad \operatorname{res}(G)=2, \qquad \Delta(G)=2.\] Therefore, \[\frac{a(G)+\operatorname{res}(G)}{\Delta(G)}=\frac{5}{2}>2=\alpha(G).\] This proves both claims. ◻
Proposition 25 (Small sharp witnesses). The inequality in Theorem 23 is attained by several connected graphs, including \(P_3\), \(C_3\), \(C_4\), and \(K_4\).
Proof. The required values are obtained directly from the definitions and from the Havel–Hakimi reduction. For example, \[\begin{array}{c|cccc} G&\alpha(G)&a(G)&\operatorname{res}(G)&\Delta(G)\\ \hline P_3&2&2&2&2\\ C_3&1&1&1&2\\ C_4&2&2&2&2\\ K_4&1&2&1&3 \end{array}\] In each row, \(\Delta(G)\alpha(G)=a(G)+\operatorname{res}(G)\). ◻
Remark 26. This section illustrates the intended role of automated conjecturing. TxGraffiti supplied a compact, human-readable, table-true inequality involving three independently studied invariants. The proof above uses neither the finite table nor optimization; the table output instead identifies the correct combination of invariants, while the theorem follows from annihilating decompositions, Brooks’ theorem, the forest bound, and the residue inequality.
Comparison with Gupta’s Caro–Wei proof↩︎
Gupta’s proof of the same TxGraffiti inequality is stronger at the degree-sequence level: it proves \[a(G)\leq \frac{\Delta(G)+1}{2}W(G),\] where \(W(G)=\sum_{v\in V(G)}1/(d(v)+1)\) is the Caro–Wei sum [33]. Together with the standard bounds recalled in Theorem 20, this immediately yields the TxGraffiti inequality for connected graphs of maximum degree at least three; maximum degree two is then handled directly. Corollary 8 records a useful consequence: for \(\Delta\geq3\), the TxGraffiti lower bound \((a+\operatorname{res})/\Delta\) is dominated by the older residue bound \(\operatorname{res}\).
Our proof is complementary. It does not use the Caro–Wei sum; instead, it derives the coarser but structural estimate \[a(G)\leq(\Delta(G)-1)\alpha(G)\] from annihilating decompositions and the matching-number theory developed above. Theorem 22 extracts the slack hidden in Gupta’s argument and turns it into the exact identity \[a(G)+\sigma_\Delta(G)=\frac{\Delta(G)+1}{2}W(G).\] Combining this identity with our exact matching theorem gives the combined bracket in Corollary 6 and the Gupta–residue annihilation-gap bound in Corollary 7, while Corollary 8 quantifies exactly how far the TxGraffiti lower bound lies below the residue bound when \(\Delta(G)\geq3\).
8 Concluding remarks↩︎
We have given a sharp matching-number theory for the annihilation gap \(a(G)-\alpha(G)\) in several natural graph classes. The arbitrary-graph theorem gives a closed exact bound in terms of \(\mu(G)\), while the forest, bipartite, and König–Egerváry theorems explain how the extremal value changes under classical structure. The TxGraffiti section then shows that these annihilation methods give an independent structural proof of a machine-generated inequality involving the annihilation number, the Havel–Hakimi residue, and maximum degree, complementing the recent Caro–Wei proof of Gupta. Combining the two approaches yields the bracket in Corollary 6 and the Gupta–residue gap bound in Corollary 7, while Corollary 5 identifies equality in Gupta’s Caro–Wei annihilation bound by explicit degree-sequence conditions and Corollary 9 characterizes equality in the TxGraffiti inequality in terms of the same slack. Thus the slack term \(\sigma_\Delta(G)\) measures exactly the loss in Gupta’s inequality and relates the computable quantities \(\operatorname{res}(G)\), \(W(G)\), \(a(G)\), \(\mu(G)\), and \(\Delta(G)\) to \(\alpha(G)\).
The equality cases of the two principal estimates are now also isolated at the level needed for the present paper. Theorem 18 gives a matching-cover defect criterion for equality in the exact arbitrary-graph matching bound: for \(\mu\geq3\), equality is equivalent to one of two parameter alternatives with defect zero or defect one. Theorem 7 gives a structural template for the connected bipartite real-equality case, including the precise role of the cross-edges. A full isomorphism-level enumeration of the possible defect-zero/defect-one decompositions and of the possible bipartite cross-edge patterns is a natural sequel problem, but it is no longer needed for the sharp inequalities themselves. Finally, forbidding cliques leads to a different fixed-matching extremal theory; that direction is pursued in a separate sequel focused on the exact \(K_4\)-free function, matched cores, and bounded blow-up type graphs.
The sequel also gives useful context for the scope of the present methods. Once a maximum matching is fixed, its \(K_4\)-free candidates are encoded by finite matched cores and bounded blow-ups of type graphs. A fixed-defect form of the Tutte–Berge maximum-matching formula [48], [49], together with a Gallai-defect viewpoint [50], organizes the sequel’s frontier obstructions. These observations are not needed for the proofs above, but they explain why the unrestricted extremal construction in Theorem 15 is clique-driven, while forbidding \(K_4\) leads to a different reservoir-and-blow-up theory. In that sequel, the Turan–Zykov viewpoint and bounded-matching Turan input [51]–[54] enter only after the matching-core structure has been isolated.
9 Computational reproducibility notes↩︎
The computations in this appendix are not used in the proofs. They are included to make the boundary cases reproducible. For \(1\leq \mu\leq 17\), the exact arbitrary-graph value \[\Gamma(\mu)=2\mu+1-\left\lceil \sqrt{6\mu}\right\rceil\] is \[\begin{array}{c|ccccccccccccccccc} \mu&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17\\ \hline \Gamma(\mu)&0&1&2&4&5&7&8&10&11&13&14&16&18&19&21&23&24 \end{array}\] The following minimal script computes \(a(G)\) from the degree sequence and verifies the formula against any supplied finite graph list.
def annihilation_number(G):
deg = sorted(dict(G.degree()).values())
m = G.number_of_edges()
total = ans = 0
for d in deg:
if total + d <= m:
total += d
ans += 1
else:
break
return ansDeclarations↩︎
The authors declare that they have no conflict of interest.