Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 21, p. 20 — for large n, a connected graph maximizing λ₁ − d is a pineapple (Aouchiche et al.)

Proved
TaitTobin.Irregularity.theorem_21

by mikedeng1 · Oct 9, 2026 · Mathlib 0df444a (Lean v4.33.1)

extremal-graph-theorygraph-irregularityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1spectral-graph-theoryspectral-radius

There is NNN such that for every n≥Nn \ge Nn≥N the following holds. Let GGG be a connected graph on nnn vertices that maximizes

λ1(G)−d(G),d(G)=2e(G)n,\lambda_1(G) - d(G), \qquad d(G) = \frac{2e(G)}{n},λ1​(G)−d(G),d(G)=n2e(G)​,

among all connected graphs on nnn vertices, where λ1\lambda_1λ1​ is the largest adjacency eigenvalue. Then GGG is a pineapple graph: there are p,q≥0p, q \ge 0p,q≥0 with p+q=np + q = np+q=n such that

G≅PA(p,q),G \cong PA(p,q),G≅PA(p,q),

the complete graph KpK_pKp​ with qqq pendant vertices all attached to one vertex of the clique.

This proves, for all sufficiently large nnn, the conjecture of Aouchiche, Bell, Cvetković, Hansen, Rowlinson, Simić and Stevanović (2008), found by computer search, on the most irregular connected graphs in the sense of spectral radius minus average degree.

Formalization Note Only the shape is asserted: the clique size ppp is not pinned. The paper attributes the optimal clique size ⌈n/2⌉+1\lceil n/2\rceil + 1⌈n/2⌉+1 to Aouchiche et al. (Section 6) and does not prove it. The statement is one-directional; not every pineapple is a maximizer. G≅PA(p,q)G \cong PA(p,q)G≅PA(p,q) is a graph isomorphism between the vertex sets {0,…,n−1}\{0,\dots,n-1\}{0,…,n−1} and {0,…,p+q−1}\{0,\dots,p+q-1\}{0,…,p+q−1}.

Preamble
import Mathlib
import Definitions.Def_TaitTobin_Irregularity_Setting
Formal statement
namespace TaitTobin.Irregularity

open Classical WangKangXue.SpectralTuran

/-- Theorem 21, p. 20 (the conjecture of Aouchiche et al., Conjecture 3, p. 2): for `n` large, every
connected graph on `n` vertices maximizing `λ₁ − d` is isomorphic to a pineapple `PA(p, q)` with
`p + q = n`. -/
theorem theorem_21 : ∃ N : ℕ, ∀ n ≥ N, ∀ G : SimpleGraph (Fin n), IsIrregMax G →
    ∃ p q : ℕ, p + q = n ∧ Nonempty (G ≃g pineapple p q) := by sorry
end TaitTobin.Irregularity
Source
Tait and Tobin, Three conjectures in extremal spectral graph theory, arXiv:1606.01916v2, p. 20, Theorem 21 (Conjecture 3, p. 2)
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me