Tight lower bound for the spectral radius of connected graphs with given matching number

Li Tan; Xinmin Hou

REVIEW 2 major objections 4 minor 16 references

Tight lower bound for the spectral radius of connected graphs with given matching number

T0 review · 2 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Every connected graph of order n with matching number k has spectral radius at least sqrt((n+2k−3)/k), with equality precisely for a constructed family of subdivision trees when k divides n−3.

desk verdict A genuine advance with a repairable gap: the lower bound is correct, Lemma 7's proof needs fixing, and the equality characterization should be written out more carefully. read the letter →

arxiv 2607.11061 v2 pith:74HQIQT3 submitted 2026-07-13 math.CO

Xinmin Hou , Li Tan This is my paper · ORCID

classification math.CO MSC 05C5005C35

keywords spectralradiusmatchingnumberconnectedgraphsextremallowerboundSchurcomplementvertexcovertreeconstruction

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes a sharp lower bound on the spectral radius of every connected graph in terms of its order n and matching number k: ρ(G) ≥ √((n+2k−3)/k). To show the bound cannot be improved, it constructs a family of extremal trees, each obtained by subdividing the edges of a tree on k vertices and attaching pendant leaves, and proves these are the only graphs attaining equality when k divides n−3. The main theorem answers the recently posed problem of determining spectrally minimal graphs for the divisibility case, and as a corollary settles the asymptotic order of ρ(G)+k as Θ(n^{1/3}), smaller than the Θ(√n) order suggested by a previously conjectured inequality.

What carries the argument

The proof reduces to trees by deleting superfluous edges while preserving the matching number. In a tree the matching number equals the size of a minimum vertex cover X, with |X|=k and I = V∖X independent. The load-bearing device is a block partition of the adjacency matrix by X, a selected subset Y ⊆ I with |Y| ≤ k−1 making X∪Y connected, and the remaining leaves; a Schur complement (block elimination) converts the assumption ρ(G)<λ into an inequality on the number u of internal edges of X, the number of leaves, and the cross-edge counts between X and Y. The cross-term is controlled by an auxiliary graph on X, and the resulting contradiction yields the bound. The equality analysis forces u=

What would settle it

A single connected graph on n vertices with matching number k whose largest eigenvalue is strictly less than √((n+2k−3)/k) would falsify Theorem 3; such a graph, if it exists, would already appear in an exhaustive enumeration of all connected graphs on, say, n=8, k=3, where the claimed bound is about 1.915.

Watch

Extended reading notes

Core claim

The paper's central claim is that for every connected graph G on n vertices with matching number k, the largest adjacency eigenvalue satisfies ρ(G) ≥ √((n+2k−3)/k), with equality exactly for the constructed family T_{n,k}—a tree whose core is a subdivision of an arbitrary tree on k vertices with pendant leaves tuned so every core vertex has a common weighted degree c = (n+2k−3)/k. Because such trees exist precisely when k divides n−3 (and n ≥ 2k), equality is attainable exactly in that case. From this, the paper derives ρ(G)+k ≥ 3∛(n/4) for k ≥ 2, showing that the minimum of ρ+k is of order n^{1/3}.

Load-bearing premise

The proof depends on Lemma 7, which asserts that a set Y ⊆ I with |Y| ≤ k−1 can be found so that X∪Y induces a connected subgraph; the written greedy argument does not cover the case where the only vertex bridging the chosen part of X to the rest of X has already been put into Y, so the bound |Y| ≤ k−1 is not fully justified in the text as it stands.

Editorial extensions

If this is right

Every connected graph with order n and matching number k has spectral radius at least √((n+2k−3)/k), giving a single closed-form lower bound valid for all n ≥ 2k−1.
When k divides n−3, the extremal graphs are completely characterized: subdivide each edge of any tree on k vertices and attach leaves to equalize weighted degree; all such trees attain the bound.
For k ≥ 2, ρ(G)+k ≥ 3∛(n/4); thus the quantity ρ+k is Θ(n^{1/3}) and cannot be as large as Θ(√n) in the regime covered by the earlier conjecture.
The result resolves the posed determination of spectrally minimal graphs in the tight divisibility case k | (n−3), and supplies a near-minimal bound for all other cases via Corollary 8.
Since the extremal graphs are trees, the lower bound is achieved by tree-like shapes, matching the intuition from related Laplacian extremal problems.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The proof technique—selecting a small independent connector set and applying a block-elimination step to the vertex-cover block—may transfer to other spectral parameters, such as the signless Laplacian or A_α-matrix, where a matching-number constraint is combined with a fixed vertex cover.
The proposed general extremal family with weighted degrees c or c+1 is a natural conjecture for all n and k; an exhaustive computation on moderate n (say n ≤ 20) could test it directly.
The asymptotic result suggests that, for large n, the graphs minimizing ρ+k are highly unbalanced trees with k ≈ ∛(n/4), a regime quite different from the star K_{1,n−1} that is extremal only for k=1.
If the bound is tight for all divisibility cases, the next natural step is to determine the exact minimum for the remaining residue classes and to check whether the 'equality characterizes T_{n,k}' statement extends without the divisibility condition.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Worth your time. The paper proves the first general lower bound on spectral radius for connected graphs with matching number k, ρ(G) ≥ sqrt((n+2k-3)/k), and settles the asymptotic order of ρ+k as Θ(n^{1/3}). The main theorem appears correct, and the Schur complement argument is sound. The extremal family T_{n,k} (subdivide a tree on k vertices, attach leaves to equalize a weighted degree) is natural, and the Perron-Frobenius verification is clean.

The soft spot is Lemma 7. The greedy proof asserts that whenever A≠X, some y∈I\B connects A to X\A. That is false as written: the only crossing edge can be from an already-selected y∈B to X\A. A concrete counterexample is the tree with X={x1,x2,x3}, I={y1,y2,y3}, y1 adjacent to all three X-vertices, y2 a leaf at x1, y3 a leaf at x2: starting with A={x1}, choosing y1, then A={x1,x2}, no vertex in I\B touches both A and X\A. So the induction stalls. The lemma itself is true — take a spanning tree of the auxiliary graph on X where edges are X-X edges or common I-neighbors, and pick the Y-vertices realizing the k-1 auxiliary edges — but the written proof does not establish it. The lower bound does not actually need the size bound |Y|≤k-1; taking Y=I already makes the auxiliary graph connected, so the proof can be patched easily. The equality characterization does use |Y|=k-1, so that part needs the repaired Lemma 7.

The equality analysis is compressed. The claims that j is an eigenvector of BB^T+CC^T and that each y has degree 2 in X are correct once eG is known to be a tree, but the derivation is sketched rather than shown. Also, the statement of Theorem 3 ("equality holds iff G∈T_{n,k}") should acknowledge that T_{n,k} is only defined when k|(n-3); as written, the reader has to infer that non-divisibility means equality is simply unattained. The paper does discuss existence of T_{n,k} in passing, so this is a presentational issue, not a mathematical one.

Citations look appropriate; the only external dependence is Lemma 6 from Liu-Lou-Trevisan, which is standard. No fitted parameters, no circularity.

Bottom line: it deserves a serious referee. The main result is important within spectral extremal graph theory and likely correct. I would send it to review with a request to fix Lemma 7 and expand the equality portion.

Referee Report

2 major / 4 minor

Summary. The paper studies connected graphs of order n with matching number k and proves the lower bound ρ(G) ≥ sqrt((n+2k-3)/k). An extremal family T_{n,k} is constructed by subdividing the edges of a tree on k vertices and attaching pendant leaves; equality is characterized for the cases k | (n-3). As a corollary, the paper obtains ρ(G)+k ≥ 3(n/4)^{1/3}, and argues that this settles the asymptotic order Θ(n^{1/3}) for ρ+k, contradicting the order suggested by the Aouchiche–Hansen conjecture.

Significance. The claimed bound is sharp and, if correct, resolves the asymptotic part of Problem 1 of Liu–Lou–Trevisan and settles the order of ρ+k. The proof strategy—minimum vertex cover plus a Schur complement computation—is elegant, and the construction is explicit with no fitted parameters. The paper is largely self-contained, relying on [10] only for the spanning-tree reduction. However, a genuine gap in Lemma 7 and an ordering problem in the equality characterization mean the submitted proof is not yet complete.

major comments (2)

[Section 2, Lemma 7] The greedy induction asserts that whenever A_{w-1} ≠ X, there exists y ∈ I\B_{w-1} adjacent to some x'∈A_{w-1} and some z∈X\A_{w-1}. This is false. For example, take the tree with X={x1,x2,x3}, Y={y}, edges yx_i, and pendant leaves at each x_i. The matching number is 3 and X is a vertex cover, but starting with A0={x1} gives B1={y}, A1={x1,x2}; the only edge leaving {x1,x2} is yx3 with y∈B1, so the induction cannot proceed. The lemma itself is true—one can prove it by taking a spanning tree of the auxiliary graph on X whose edges are X–X edges or common Y-neighbours—but the submitted proof does not establish it. Because |Y|≤k−1 is used in the equality characterization, this gap is load-bearing.
[Section 2, Characterization of equality] Condition (3) is stated before condition (4), but the formula 2d_G[X,Y](x)+d_G[X,L](x)=c is valid only after proving that every y∈Y has exactly two X-neighbours. Equality in the chain gives only (BB^T+CC^T)j=λ^2j; the contribution of a y∈Y is d_Y(y), not 2. The proof should first use u=0, |Y|≤k−1, and connectedness of eG to force d_Y(y)=2 for all y∈Y (d_Y≥3 creates a triangle in eG; d_Y=1 would force |Y|>k−1), and then derive the constant weighted-degree condition. This is a logical-ordering issue in the equality characterization, not an error in the final statement.

minor comments (4)

[Section 2, after Eq. (5)] The sentence "Since u > 0, T must contain a path of length 3" is not justified by u>0 alone. It follows from k≥2 (a matching number at least 2 gives two disjoint edges, hence a P4 subgraph). Please add a clarifying sentence.
[Section 2, equality paragraph] The statement "The equality condition k | (n-3) follows from the requirement that (n+2k-3)/k be an integer" should be qualified. Divisibility is necessary but not sufficient for the existence of an extremal graph: for k=3, n=6, k | (n-3) but no T1 on 3 vertices satisfies 2d_T1(x_i) ≤ c=3. The Construction 2 note for k≥4 should be echoed here.
[Proposition 4] The proof that the constructed graph has matching number exactly k is terse. In particular, the assertion about the leaves of T_{2k-2} requires a short justification. A few explanatory sentences would improve readability.
[Throughout] Typos and typesetting: the cube root in the abstract and Corollary 5 is corrupted ("3√" / "3 3\r n"); reference [12] contains a corrupted symbol in the page range; the accent in "Stevanović" is misplaced.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the lower bound is derived independently of the extremal construction, and no fitted input is renamed as a prediction.

full rationale

The central derivation in Section 2 is self-contained: it reduces to trees via an external lemma from Liu–Lou–Trevisan, then uses König's theorem, a Schur complement argument, and an auxiliary graph bound. The extremal family T_{n,k} is deliberately constructed with c=(n+2k−3)/k and f_i=c−2d_{T_1}(x_i) so that the proposed bound is attained; this is a tightness construction, not a fitted parameter later called a prediction. The equality characterization is obtained by tracing equality through the inequalities (u=0, |Y|=k−1, j a Perron eigenvector, and no Y-vertex adjacent to three vertices of X), not by importing the construction as an assumption. The application corollary follows algebraically from the proved bound and the verified construction. References to the authors' earlier work appear only as background, not as load-bearing support. The written proof of Lemma 7 has a gap noted in the reader's analysis, but that is a correctness issue, not circularity. Accordingly, no circular step is identified.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No fitted constants; the bound and extremal construction are determined entirely by n and k. The proof rests on standard Perron–Frobenius, König, and Schur complement results, plus the cited spanning-tree lemma 6 from [10]. Lemma 7 is a new structural lemma proved (with a gap) in the paper. No new entities are postulated.

assumptions (5)

standard math Perron–Frobenius theorem for connected nonnegative matrices: the spectral radius is the unique largest eigenvalue and has a positive eigenvector.
Invoked in Proposition 4 to identify the constructed positive eigenvector with ρ(G), and in the proof to argue λI − A(G) is positive definite iff ρ(G) < λ.
standard math König's theorem: in bipartite graphs, maximum matching size equals minimum vertex cover size.
Used in Section 2 to choose a minimum vertex cover X of size k and to conclude I = V(G)\X is independent.
standard math Schur complement / congruence preserves positive definiteness.
Used to derive the block-matrix inequality in Section 2 from the assumption ρ(G) < λ.
domain assumption Lemma 6 from [10]: a connected graph with matching number k has a spanning tree with matching number k.
Taken from the cited paper without proof; it reduces the problem from general connected graphs to trees and is load-bearing for the lower bound.
domain assumption If a minimum vertex cover X of a tree with n ≥ 2k ≥ 4 contains an edge, the tree contains a path with 4 vertices (P4).
Used in the final contradiction for k ≥ 2; asserted without proof in the text ('When k ≥ 2, T must contain a path of length 3') and depends on structural properties of minimum vertex covers.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Tight lower bound for the spectral radius of connected graphs with given matching number." pith.science (2026). https://pith.science/paper/74HQIQT3

@misc{pith2026260711061,
  author       = {Pith},
  title        = {Pith review of: Tight lower bound for the spectral radius of connected graphs with given matching number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/74HQIQT3}},
  note         = {Machine review of arXiv:2607.11061}
}

abstract

Let $\mathscr{G}_{n,k}$ denote the family of all connected graphs of order $n$ with matching number $k$. Liu, Lou, and Trevisan~(Linear Algebra Appl., 2026) posed the following problem: Determine the spectrally minimal graphs in $\mathscr{G}_{n,k}$. In this paper we prove that for every graph $G \in \mathscr{G}_{n,k}$, $ \rho(G) \ge \sqrt{\frac{n + 2k - 3}{k}}, $ and we completely characterize the extremal graphs when $k \mid (n-3)$. As applications, we establish $\rho(G) + k \ge 3\sqrt[3]{n/4}$ for $k \ge 2$, settling the asymptotic order of $\rho + k$ as $\Theta(n^{1/3})$ -- strictly smaller than the $\Theta(\sqrt{n})$ order suggested by the disproved Aouchiche--Hansen conjecture.

Figures

Figures reproduced from arXiv: 2607.11061 by the authors.

**Figure 2.** An extremal graph for k = 10 with a non-path, non-star tree T1. 3 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 1 linked inside Pith

[10]

J. Liu, Z. Lou, V. Trevisan, Minimal spectral radius of graphs with given matching number, Linear Algebra Appl., 746 (2026), 88-110

2026
[1]

Aouchiche, P

M. Aouchiche, P. Hansen, A survey of automated conjectures in spectral graph theory, Linear Algebra Appl. 432 (2010) 2293–2322

2010
[2]

Chang, On the largest eigenvalue of a tree with perfect matchings, Discrete Math

A. Chang, On the largest eigenvalue of a tree with perfect matchings, Discrete Math. 269 (2003) 45–63

2003
[3]

S. M. Cioabă, Perfect matchings, eigenvalues and expansion, C. R. Math. Acad. Sci. Soc. R. Can. 27 (2005) 101–104

2005
[4]

Collatz, U

L. Collatz, U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Semin. Univ. Hambg. 21 (1957) 63–77. 9

1957
[5]

Y. P. Hou, J. S. Li, Bounds on the largest eigenvalues of trees with a given size of matching, Linear Algebra Appl. 342 (2002) 203–217

2002
[6]

L. Feng, G. Yu, X. Zhang, Spectral radius of graphs with given matching number, Linear Algebra Appl. 422 (2007) 133–138

2007
[7]

König, Graphok és matrixok (Graphs and matrices), Matematikai és Fizikai Lapok 38 (1931) 116–119

D. König, Graphok és matrixok (Graphs and matrices), Matematikai és Fizikai Lapok 38 (1931) 116–119

1931

Show all 16 references

[8]

W. Li, A. Chang, The minimal Laplacian spectral radius of trees with given matching number, Linear Multilinear Algebra 62 (2014) 218–228

2014
[9]

W. S. Lin, X. F. Guo, On the largest eigenvalues of trees with perfect matchings, J. Math. Chem. 42 (2007) 1057–1067

2007
[11]

Stevanović

D. Stevanović. Resolution of AutoGraphiX conjectures relating the index and matching number of graphs. Linear algebra and its applications, 433 (2010), 1674-1677

2010
[12]

Sun, T.M

W.L. Sun, T.M. Sun, J.-M. Guo, S.W. Tan, On the minimum spectral radius of trees with given matching number, Ars Comb. 134 (2017) 111 ⚶⚶134

2017
[13]

A. Z. Wagner, Constructions in combinatorics via neural networks, arXiv:2104.14516, 2021

2021 arXiv
[14]

H. Wang, X. Hou, Y. Ma, Spectral extrema of graphs with bounded clique number and matching number, Linear Algebra Appl. 669 (2023) 125–135

2023
[15]

X. Yuan, Z. Shao, On the maximal α-spectral radius of graphs with given matching number, Linear Multilinear Algebra 70 (2022), no. 20, 5515–5524

2022
[16]

M. Q. Zhai, J. Xue, R. F. Liu, An extremal problem on Q-spectral radii of graphs with given size and matching number, Linear Multilinear Algebra 70 (2022) 5334–5345. 10

2022

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [10]

J. Liu, Z. Lou, V. Trevisan, Minimal spectral radius of graphs with given matching number, Linear Algebra Appl., 746 (2026), 88-110

2026

[2] [1]

Aouchiche, P

M. Aouchiche, P. Hansen, A survey of automated conjectures in spectral graph theory, Linear Algebra Appl. 432 (2010) 2293–2322

2010

[3] [2]

Chang, On the largest eigenvalue of a tree with perfect matchings, Discrete Math

A. Chang, On the largest eigenvalue of a tree with perfect matchings, Discrete Math. 269 (2003) 45–63

2003

[4] [3]

S. M. Cioabă, Perfect matchings, eigenvalues and expansion, C. R. Math. Acad. Sci. Soc. R. Can. 27 (2005) 101–104

2005

[5] [4]

Collatz, U

L. Collatz, U. Sinogowitz, Spektren endlicher Grafen, Abh. Math. Semin. Univ. Hambg. 21 (1957) 63–77. 9

1957

[6] [5]

Y. P. Hou, J. S. Li, Bounds on the largest eigenvalues of trees with a given size of matching, Linear Algebra Appl. 342 (2002) 203–217

2002

[7] [6]

L. Feng, G. Yu, X. Zhang, Spectral radius of graphs with given matching number, Linear Algebra Appl. 422 (2007) 133–138

2007

[8] [7]

König, Graphok és matrixok (Graphs and matrices), Matematikai és Fizikai Lapok 38 (1931) 116–119

D. König, Graphok és matrixok (Graphs and matrices), Matematikai és Fizikai Lapok 38 (1931) 116–119

1931