AFTD Auto-Formalizing Theoretical Domains

laplacian_mu2_le_mu1

theoremverified

For any finite vertex type V and any simple graph G on V with at least 2 vertices (2 ≤ Fintype.card V), the second largest Laplacian eigenvalue is at most the largest Laplacian eigenvalue: laplacian_mu2 G ≤ laplacian_mu1 G.

Statement

theorem laplacian_mu2_le_mu1 {V : Type*} [Fintype V] (G : SimpleGraph V) (hV : 2 ≤ Fintype.card V) :
    laplacian_mu2 G ≤ laplacian_mu1 G
Source
folklore
Verified
05 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • laplacian_mu1For any finite vertex type V and any simple graph G on V, the largest eigenvalue μ₁ (Laplacian spectral radius) of the real Laplacian…
  • laplacian_mu2For any finite vertex type V and any simple graph G on V, the second largest eigenvalue μ₂ of the real Laplacian matrix L = D - A of G,…

Read back from the Lean

For every finite type V (with instance [Fintype V]), every simple graph G on V, and every hypothesis hV that V has cardinality at least 2 (2 ≤ Fintype.card V), laplacian_mu2 G is less than or equal to laplacian_mu1 G.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The eigenvalues μ₂ and μ₁ are defined as the Laplacian matrix eigenvalues at indices 1 and 0, guarded by conditions on the vertex count |V|. Because |V| ≥ 2, both conditions hold, and unfolding the definitions reduces the claim to comparing the eigenvalues at indices 1 and 0 directly. Since the eigenvalues of a Hermitian matrix are arranged in descending order (eigenvalues₀_antitone), the eigenvalue at index 1 is at most that at index 0 because 0 ≤ 1.

  1. The inequality reduces to showing that the Laplacian eigenvalue at index 1 is at most the Laplacian eigenvalue at index 0.

    We enable classical logic and unfold the definitions of laplacian_mu2 and laplacian_mu1. Both definitions check whether the vertex count |V| is sufficiently large (at least 2 and at least 1, respectively) via a dependent if-then-else. Since |V| ≥ 2 by hypothesis (hV), integer linear arithmetic (omega) yields 1 ≤ |V|. Using dif_pos with both inequalities simplifies both conditionals to their true branches, leaving the goal of showing that the Laplacian matrix eigenvalue at index 1 is at most the eigenvalue at index 0.

    lines 4–7

    uses dif_pos

      classical
      dsimp [laplacian_mu2, laplacian_mu1]
      have h1 : 1 ≤ Fintype.card V := by omega
      rw [dif_pos hV, dif_pos h1]
  2. The Laplacian eigenvalue at index 1 is at most the Laplacian eigenvalue at index 0.

    The eigenvalues of a Hermitian matrix (eigenvalues₀) are ordered in descending order, as asserted by eigenvalues₀_antitone. Applying this antitone property reduces the inequality between eigenvalues to the inequality between their indices in reverse, 0 ≤ 1. This index inequality is immediate from Nat.zero_le.

    lines 8–9

    uses eigenvalues₀_antitone, Nat.zero_le

      apply (G.isHermitian_lapMatrix ℝ).eigenvalues₀_antitone
      exact Nat.zero_le 1
dif_pos
If a proposition c holds, then the dependent if-then-else expression (dite c t e) evaluates to the "then" branch t hc.
eigenvalues₀_antitone
The eigenvalue sequence hA.eigenvalues₀ of a Hermitian matrix is antitone (monotonically decreasing with respect to index).
Nat.zero_le
Zero is less than or equal to any natural number n.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- The second largest Laplacian eigenvalue is at most the largest Laplacian eigenvalue. -/theorem laplacian_mu2_le_mu1 {V : Type*} [Fintype V] (G : SimpleGraph V) (hV : 2 ≤ Fintype.card V) :    laplacian_mu2 G ≤ laplacian_mu1 G := by  classical  dsimp [laplacian_mu2, laplacian_mu1]  have h1 : 1 ≤ Fintype.card V := by omega  rw [dif_pos hV, dif_pos h1]  apply (G.isHermitian_lapMatrix ℝ).eigenvalues₀_antitone  exact Nat.zero_le 1
See it in the graphDiscuss this resultChallenge it