laplacian_mu2_le_mu1
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.
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.
uses
dif_posclassical dsimp [laplacian_mu2, laplacian_mu1] have h1 : 1 ≤ Fintype.card V := by omega rw [dif_pos hV, dif_pos h1]
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.
uses
eigenvalues₀_antitone,Nat.zero_leapply (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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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