AFTD Auto-Formalizing Theoretical Domains

adjacency_lambda2_eq_of_charpoly_roots

theoremverified

For a simple graph G on a finite vertex set, if the roots of the characteristic polynomial of its real adjacency matrix are a, x and a multiset M with x ≤ a and every element of M at most x, then the second largest adjacency eigenvalue adjacency_lambda2 G equals x.

Statement

open scoped Classical in
theorem adjacency_lambda2_eq_of_charpoly_roots
    {V : Type*} [Fintype V] (G : SimpleGraph V) (a x : ℝ) (M : Multiset ℝ)
    (hroots : (G.adjMatrix ℝ).charpoly.roots = a ::ₘ x ::ₘ M)
    (hxa : x ≤ a) (hM : ∀ y ∈ M, y ≤ x) :
    adjacency_lambda2 G = x
Source
arXiv:2611.00591, Lemma 4.1 (step of its proof)
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • adjacency_lambda2For any finite vertex type V and any simple graph G on V, the eigenvalue at index 1 of the real adjacency matrix (G.isHermitian_adjMatrix…
Used by 1

The proof, explained

The adjacency matrix of a simple graph is real symmetric, so its eigenvalues in descending order coincide with the roots of its characteristic polynomial sorted in non-increasing order. Given that the roots are a, x, and a multiset M with x ≤ a and all elements of M at most x, the sorted list of eigenvalues begins with a followed by x. Since this list has length at least 2, the second eigenvalue adjacency_lambda2 G is well-defined and equals the entry at index 1, which is x.

  1. The list of eigenvalues of the adjacency matrix sorted in descending order equals a :: x :: M.sort (≥).

    The real adjacency matrix of a simple graph is symmetric (Hermitian), so by the spectral theorem (sort_roots_charpoly_eq_eigenvalues₀), its eigenvalues sorted in descending order coincide with the roots of its characteristic polynomial sorted in descending order. Since the roots are real, taking their real parts via RCLike.re is the identity function (using Multiset.map_id). Substituting the known roots a ::ₘ x ::ₘ M and applying Multiset.sort_cons twice pulls a and x to the front, yielding a :: x :: M.sort (≥).

    lines 7–13

    uses Multiset.map_id, Multiset.sort_cons

      have hA := G.isHermitian_adjMatrix ℝ
      have hsort := hA.sort_roots_charpoly_eq_eigenvalues₀
      have hre : (G.adjMatrix ℝ).charpoly.roots.map RCLike.re =
          (G.adjMatrix ℝ).charpoly.roots := by
        conv_rhs => rw [← Multiset.map_id (G.adjMatrix ℝ).charpoly.roots]
        rfl
      rw [hre, hroots, Multiset.sort_cons, Multiset.sort_cons] at hsort
  2. The vertex set of G has cardinality at least 2 (2 ≤ |V|).

    Applying List.length to both sides of the sorted eigenvalue equality via congrArg shows that the list of eigenvalues has length |V| (by List.length_ofFn), while the list a :: x :: M.sort (≥) has length |M| + 2 (by List.length_cons). Linear arithmetic (omega) immediately yields 2 ≤ |V|.

    lines 14–16

    uses congrArg, List.length_cons, List.length_ofFn

      · have hlen := congrArg List.length hsort
        simp only [List.length_cons, List.length_ofFn] at hlen
        have hn : 2 ≤ Fintype.card V := by omega
  3. adjacency_lambda2 G = x

    Unfolding the definition of adjacency_lambda2 G, the condition 2 ≤ |V| holds, so dif_pos reduces the expression to the eigenvalue at index 1 (the second eigenvalue). Evaluating both sides of the sorted list equality at index 1 via congrArg, the second entry of a :: x :: M.sort (≥) is x (by List.getElem?_cons_succ and List.getElem?_cons_zero), which matches the second eigenvalue (by List.getElem?_ofFn).

    lines 17–23

    uses dif_pos, congrArg, List.getElem?_cons_succ, List.getElem?_cons_zero, List.getElem?_ofFn

        unfold adjacency_lambda2
        rw [dif_pos hn]
        have := congrArg (fun l => l[1]?) hsort
        simp only [List.getElem?_cons_succ, List.getElem?_cons_zero, List.getElem?_ofFn] at this
        simp at this
        obtain ⟨_, hx⟩ := this
        exact hx.symm
  4. Every element of M is at most x (∀ b ∈ M, x ≥ b).

    This is directly the hypothesis hM, discharging the first sorting condition needed to pull x to the front of M.sort (≥).

    line 24

      · exact fun b hb => hM b hb
  5. Every element of x ::ₘ M is at most a (∀ b ∈ x ::ₘ M, a ≥ b).

    Any element b in x ::ₘ M either equals x or belongs to M (by Multiset.mem_cons.mp). If b = x, then b ≤ a by hypothesis hxa. If b ∈ M, then b ≤ x ≤ a by hypothesis hM and transitivity with hxa. This discharges the second sorting condition needed to pull a to the front.

    lines 25–28

    uses Multiset.mem_cons.mp

      · intro b hb
        rcases Multiset.mem_cons.mp hb with rfl | hb
        · exact hxa
        · exact (hM b hb).trans hxa
Multiset.map_id
Mapping the identity function over any multiset leaves the multiset unchanged.
Multiset.sort_cons
If an element a satisfies r a b for all b in a multiset s, then sorting the multiset a ::ₘ s by r yields a prepended to the sorted list of s.
congrArg
Applying a function to both sides of an equality preserves the equality: if a₁ = a₂, then f(a₁) = f(a₂).
List.length_cons
Prepending an element to a list increases its length by 1.
List.length_ofFn
The length of the list generated from a function with domain Fin n is n.
dif_pos
A dependent if-then-else evaluates to its 'then' branch when the condition is satisfied.
List.getElem?_cons_succ
The element at index i + 1 in a list a :: l is the element at index i in the tail l.
List.getElem?_cons_zero
The element at index 0 in a list a :: l is the head element a.
List.getElem?_ofFn
The element at index i of a list formed by List.ofFn f of size n is some (f i) if i < n, and none otherwise.
Multiset.mem_cons.mp
An element belongs to a ::ₘ s if and only if it equals a or belongs to s.

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

open scoped Classical intheorem adjacency_lambda2_eq_of_charpoly_roots    {V : Type*} [Fintype V] (G : SimpleGraph V) (a x : ℝ) (M : Multiset ℝ)    (hroots : (G.adjMatrix ℝ).charpoly.roots = a ::ₘ x ::ₘ M)    (hxa : x ≤ a) (hM : ∀ y ∈ M, y ≤ x) :    adjacency_lambda2 G = x := by  have hA := G.isHermitian_adjMatrix ℝ  have hsort := hA.sort_roots_charpoly_eq_eigenvalues₀  have hre : (G.adjMatrix ℝ).charpoly.roots.map RCLike.re =      (G.adjMatrix ℝ).charpoly.roots := by    conv_rhs => rw [← Multiset.map_id (G.adjMatrix ℝ).charpoly.roots]    rfl  rw [hre, hroots, Multiset.sort_cons, Multiset.sort_cons] at hsort  · have hlen := congrArg List.length hsort    simp only [List.length_cons, List.length_ofFn] at hlen    have hn : 2 ≤ Fintype.card V := by omega    unfold adjacency_lambda2    rw [dif_pos hn]    have := congrArg (fun l => l[1]?) hsort    simp only [List.getElem?_cons_succ, List.getElem?_cons_zero, List.getElem?_ofFn] at this    simp at this    obtain ⟨_, hx⟩ := this    exact hx.symm  · exact fun b hb => hM b hb  · intro b hb    rcases Multiset.mem_cons.mp hb with rfl | hb    · exact hxa    · exact (hM b hb).trans hxa
See it in the graphDiscuss this resultChallenge it