Theorem 21, p. 20 — for large n, a connected graph maximizing λ₁ − d is a pineapple (Aouchiche et al.)
ProvedTaitTobin.Irregularity.theorem_21There is such that for every the following holds. Let be a connected graph on vertices that maximizes
among all connected graphs on vertices, where is the largest adjacency eigenvalue. Then is a pineapple graph: there are with such that
the complete graph with pendant vertices all attached to one vertex of the clique.
This proves, for all sufficiently large , 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 is not pinned. The paper attributes the optimal clique size to Aouchiche et al. (Section 6) and does not prove it. The statement is one-directional; not every pineapple is a maximizer. is a graph isomorphism between the vertex sets and .
import Mathlib import Definitions.Def_TaitTobin_Irregularity_Setting
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.