A proof of Haemers' toughness conjecture

Gary Greaves; Haoran Zhu

arxiv: 2605.15738 · v1 · pith:FYFXAPHVnew · submitted 2026-05-15 · 🧮 math.CO

A proof of Haemers' toughness conjecture

Gary Greaves , Haoran Zhu This is my paper

Pith reviewed 2026-05-20 17:33 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5005C40

keywords toughnessLaplacian eigenvaluesalgebraic connectivitygraph connectivityspectral graph theoryHaemers conjecturevertex cutsminimum degree

0 comments

The pith

For any connected graph, toughness is at least the second-smallest Laplacian eigenvalue divided by the gap between the largest eigenvalue and the minimum degree.

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

The paper proves a lower bound on graph toughness expressed directly in terms of the Laplacian spectrum. Toughness quantifies the smallest ratio of vertices removed to the number of resulting components, capturing resistance to fragmentation. The bound links this combinatorial quantity to the algebraic connectivity and the spread of Laplacian eigenvalues, offering a computable estimate that avoids enumerating all possible cuts. A sympathetic reader cares because the result settles a long-standing conjecture and supplies a spectral certificate for a classical graph parameter.

Core claim

If Γ is a connected graph with minimum degree δ and Laplacian eigenvalues 0=μ₁<μ₂≤⋯≤μₙ, then the toughness of Γ is bounded below by μ₂/(μₙ−δ).

What carries the argument

The ratio μ₂/(μₙ−δ), where μ₂ is the algebraic connectivity and μₙ the largest Laplacian eigenvalue, which is shown to lower-bound the minimum of |S|/c(Γ−S) over all vertex cuts S.

Load-bearing premise

The graph must be connected so that the Laplacian has a simple zero eigenvalue and the algebraic connectivity μ₂ is strictly positive.

What would settle it

A single connected graph whose toughness, computed by checking all vertex cuts, falls strictly below the value of its μ₂ divided by (μₙ minus δ).

read the original abstract

We prove that if $\Gamma$ is a connected graph with minimum degree $\delta$ and Laplacian eigenvalues $0=\mu_1<\mu_2\leqslant \cdots \leqslant \mu_n$, then the toughness of $\Gamma$ is bounded below by $\mu_2/(\mu_n-\delta)$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Greaves and Zhu prove Haemers' toughness conjecture with a direct argument from the Laplacian Rayleigh quotient.

read the letter

Greaves and Zhu prove Haemers' toughness conjecture in this paper. The key result is that for any connected graph Γ with min degree δ and Laplacian eigenvalues 0 = μ1 < μ2 ≤ ... ≤ μn, the toughness t(Γ) is at least μ2 over (μn minus δ). What stands out is that they deliver a complete proof rather than another partial result. The derivation uses the minimax property of the algebraic connectivity μ2 and constructs a suitable test vector from a minimum toughness cut. This links the combinatorial toughness directly to the spectral gap and the upper end of the spectrum. The paper does this cleanly. It avoids extra assumptions and works from the basic definitions of the Laplacian quadratic form and the toughness parameter. The stress test confirms the steps rely only on standard facts about the Rayleigh quotient and bounding the contribution from cut edges via μn. Connectedness is used precisely to make μ2 positive, which is necessary. One soft spot is that the resulting bound can be quite weak when μn is much larger than δ, which happens in many graphs. But the authors present it as a lower bound without claiming it is always sharp, so that is not a flaw in the argument itself. Another thing is that the proof is for connected graphs only, leaving open what happens in the disconnected case, though toughness is usually discussed for connected graphs anyway. Readers in spectral graph theory will get the most from this, especially those interested in how algebraic connectivity relates to vertex expansion and toughness. It organizes some existing ideas around these parameters. I think this paper merits a serious referee. The central claim is a named conjecture that has been around for decades, and the proof appears self-contained and verifiable. It is worth the time to check the details in the full manuscript.

Referee Report

0 major / 2 minor

Summary. The manuscript proves Haemers' toughness conjecture: if Γ is a connected graph with minimum degree δ and Laplacian eigenvalues 0=μ₁<μ₂≤⋯≤μₙ, then the toughness t(Γ) is at least μ₂/(μₙ−δ). The argument proceeds from the Rayleigh-quotient characterization of algebraic connectivity μ₂ together with a test vector assembled from the components of a minimum-toughness vertex cut, using only the definition of the Laplacian quadratic form and the bound μₙ on the maximum quadratic contribution from cut edges.

Significance. If correct, the result supplies an explicit, parameter-free spectral lower bound on toughness that resolves a known conjecture in spectral graph theory. The derivation is self-contained, invokes the connectedness hypothesis only to guarantee μ₂>0, and avoids hidden normalizations or post-hoc adjustments. This constitutes a clean contribution to the literature relating Laplacian spectra to connectivity parameters.

minor comments (2)

In the statement of the main theorem (presumably §1 or the abstract), the inequality is written with ≤ for the ordered eigenvalues; confirm that the proof treats the case of repeated eigenvalues correctly when constructing the test vector.
The manuscript would benefit from an explicit sentence recalling the definition of toughness t(Γ) = min |S|/c(Γ−S) immediately before the proof, to make the cut-vector construction self-contained for readers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive evaluation of our manuscript and the recommendation to accept. The referee's summary correctly identifies the core elements of the proof, including the use of the Rayleigh quotient for algebraic connectivity and the construction of the test vector from a minimum-toughness cut.

Circularity Check

0 steps flagged

No significant circularity; direct derivation from definitions

full rationale

The manuscript derives the toughness lower bound directly from the Rayleigh quotient applied to the algebraic connectivity eigenvector, combined with a test vector constructed from the components of a minimum-toughness cut. All steps invoke only the definition of the Laplacian quadratic form, the minimax characterization of μ₂, and the fact that μₙ bounds the quadratic-form contribution from cut-incident edges. Connectedness is used solely to guarantee μ₂ > 0 and is not extended. No parameter is fitted and then relabeled as a prediction, no self-citation supplies a load-bearing uniqueness theorem, and no ansatz is smuggled in. The central inequality therefore reduces to standard spectral-graph-theory identities rather than to any quantity defined in terms of the target bound itself.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof rests on the standard axiomatic framework of spectral graph theory (Laplacian matrix properties, connectedness implying μ₁=0 with multiplicity 1) and the classical definition of toughness; no new free parameters, invented entities, or ad-hoc assumptions are introduced.

axioms (2)

standard math The Laplacian matrix L = D − A of a simple undirected graph has smallest eigenvalue 0 with eigenvector the all-ones vector precisely when the graph is connected.
Invoked to guarantee μ₁ = 0 and μ₂ > 0.
domain assumption Toughness t(Γ) is defined as the minimum of |S| / c(Γ − S) over all vertex cuts S that increase the number of components.
Central definition used to state the conjecture and the proved bound.

pith-pipeline@v0.9.0 · 5556 in / 1433 out tokens · 134003 ms · 2026-05-20T17:33:30.228738+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 1.1: t(Γ) ≥ μ₂/(μ_n - δ) proved via vertex-cut partition π = {H1,...,Hc,U} and positive-semidefiniteness of μ_n I - Q_π(L(Γ))

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

12 extracted references · 12 canonical work pages

[1]

Alon,Tough Ramsey graphs without short cycles, J

N. Alon,Tough Ramsey graphs without short cycles, J. Algebraic Combin. 4(1995), no. 3, 189–195

work page 1995
[2]

Bauer, H

D. Bauer, H. Broersma, and E. Schmeichel,Toughness in graphs – a survey, Graphs Combin. 22 (2006), no. 1, 1–35

work page 2006
[3]

Brouwer,Toughness and spectrum of a graph, Linear Algebra Appl

A.E. Brouwer,Toughness and spectrum of a graph, Linear Algebra Appl. 226–228(1995), 267–271

work page 1995
[4]

Brouwer and W.H

A.E. Brouwer and W.H. Haemers,Spectra of graphs, Springer, New York, 2012

work page 2012
[5]

Chvátal,Tough graphs and Hamiltonian circuits, Discrete Math.5 (1973), 215–228

V. Chvátal,Tough graphs and Hamiltonian circuits, Discrete Math.5 (1973), 215–228

work page 1973
[6]

Cioabă and X

S.M. Cioabă and X. Gu,Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs, Czech. Math. J. 66(141) (2016), no. 3, 913–924

work page 2016
[7]

Cioabă and W

S.M. Cioabă and W. Wong,The spectrum and toughness of regular graphs, Discrete Appl. Math.176(2014), 43–52

work page 2014
[8]

Fiedler,Algebraic connectivity of graphs, Czech

M. Fiedler,Algebraic connectivity of graphs, Czech. Math. J.23(1973), 298–305

work page 1973
[9]

Gu,A proof of Brouwer’s toughness conjecture, SIAM J

X. Gu,A proof of Brouwer’s toughness conjecture, SIAM J. Discrete Math.35(2021), no. 2, 948–952

work page 2021
[10]

Gu,Toughness in pseudo-random graphs, European J

X. Gu,Toughness in pseudo-random graphs, European J. Combin.92 (2021), Paper No. 103255

work page 2021
[11]

Gu and W.H

X. Gu and W.H. Haemers,Graph toughness from Laplacian eigenvalues, Algebraic Combin.5(2022), no. 1, 53–61

work page 2022
[12]

Haemers,Toughness conjecture, posted in ResearchGate, (2020), available at https://www.researchgate.net/publication/348437253 (last checked 05/05/2026)

W.H. Haemers,Toughness conjecture, posted in ResearchGate, (2020), available at https://www.researchgate.net/publication/348437253 (last checked 05/05/2026). 9

work page arXiv 2020

[1] [1]

Alon,Tough Ramsey graphs without short cycles, J

N. Alon,Tough Ramsey graphs without short cycles, J. Algebraic Combin. 4(1995), no. 3, 189–195

work page 1995

[2] [2]

Bauer, H

D. Bauer, H. Broersma, and E. Schmeichel,Toughness in graphs – a survey, Graphs Combin. 22 (2006), no. 1, 1–35

work page 2006

[3] [3]

Brouwer,Toughness and spectrum of a graph, Linear Algebra Appl

A.E. Brouwer,Toughness and spectrum of a graph, Linear Algebra Appl. 226–228(1995), 267–271

work page 1995

[4] [4]

Brouwer and W.H

A.E. Brouwer and W.H. Haemers,Spectra of graphs, Springer, New York, 2012

work page 2012

[5] [5]

Chvátal,Tough graphs and Hamiltonian circuits, Discrete Math.5 (1973), 215–228

V. Chvátal,Tough graphs and Hamiltonian circuits, Discrete Math.5 (1973), 215–228

work page 1973

[6] [6]

Cioabă and X

S.M. Cioabă and X. Gu,Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs, Czech. Math. J. 66(141) (2016), no. 3, 913–924

work page 2016

[7] [7]

Cioabă and W

S.M. Cioabă and W. Wong,The spectrum and toughness of regular graphs, Discrete Appl. Math.176(2014), 43–52

work page 2014

[8] [8]

Fiedler,Algebraic connectivity of graphs, Czech

M. Fiedler,Algebraic connectivity of graphs, Czech. Math. J.23(1973), 298–305

work page 1973

[9] [9]

Gu,A proof of Brouwer’s toughness conjecture, SIAM J

X. Gu,A proof of Brouwer’s toughness conjecture, SIAM J. Discrete Math.35(2021), no. 2, 948–952

work page 2021

[10] [10]

Gu,Toughness in pseudo-random graphs, European J

X. Gu,Toughness in pseudo-random graphs, European J. Combin.92 (2021), Paper No. 103255

work page 2021

[11] [11]

Gu and W.H

X. Gu and W.H. Haemers,Graph toughness from Laplacian eigenvalues, Algebraic Combin.5(2022), no. 1, 53–61

work page 2022

[12] [12]

Haemers,Toughness conjecture, posted in ResearchGate, (2020), available at https://www.researchgate.net/publication/348437253 (last checked 05/05/2026)

W.H. Haemers,Toughness conjecture, posted in ResearchGate, (2020), available at https://www.researchgate.net/publication/348437253 (last checked 05/05/2026). 9

work page arXiv 2020