bipartite_complement_adj_spectrum_and_lambda2
Let H be an s-regular bipartite simple graph whose two parts V and W each have size m ≥ 2, and let G = K_{V,W} \ E(H) be its bipartite complement. Then G is (m − s)-regular, and there is a multiset M of 2m − 2 reals such that the eigenvalues of the adjacency matrix of H (roots of its characteristic polynomial, with multiplicity) are s, −s and M, while those of G are m − s, −(m − s) and M. Furthermore, if m > 2s, then G is connected and its second largest adjacency eigenvalue equals that of H.
Statement
open scoped Classical in theorem bipartite_complement_adj_spectrum_and_lambda2 {V W : Type*} [Fintype V] [Fintype W] (m s : ℕ) (hm : 2 ≤ m) (hV : Fintype.card V = m) (hW : Fintype.card W = m) (H : SimpleGraph (V ⊕ W)) (hH_sub : H ≤ completeBipartiteGraph V W) (hH_reg : H.IsRegularOfDegree s) : let G := completeBipartiteGraph V W \ H G.IsRegularOfDegree (m - s) ∧ (∃ M : Multiset ℝ, Multiset.card M = 2 * m - 2 ∧ (H.adjMatrix ℝ).charpoly.roots = {(s : ℝ), -(s : ℝ)} + M ∧ (G.adjMatrix ℝ).charpoly.roots = {((m - s : ℕ) : ℝ), -((m - s : ℕ) : ℝ)} + M) ∧ (2 * s < m → G.Connected ∧ adjacency_lambda2 G = adjacency_lambda2 H)
- Formalizes
- arXiv:2611.00591, Lemma 4.1
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- bipartite_complement_regularLet H be an s-regular bipartite simple graph on parts V and W of size m. Then its bipartite complement K_{V,W} \ H is (m - s)-regular.
- bipartite_complement_connectedLet H be an s-regular bipartite simple graph on parts V and W of size m ≥ 2. If 2s < m, then the bipartite complement G = K_{V,W} \ E(H)…
- bipartite_complement_adj_charpoly_mulLet H be an s-regular graph contained in the complete bipartite graph on parts V, W of size m, and G = K_{V,W} minus H. Then…
- regular_bipartite_adj_charpoly_roots_contain_pm_degreeLet H be an s-regular graph contained in the complete bipartite graph on parts V, W of size m ≥ 1. Then s and −s are roots of the…
- regular_adj_charpoly_root_abs_leFor an s-regular simple graph G on a finite vertex set, every root μ of the characteristic polynomial of its real adjacency matrix…
- adjacency_lambda2_eq_of_charpoly_rootsFor 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…
- 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…
- three_token_k2n_domination_number_four_geThe domination number of the 3-token graph F_3(K_{2,4}) of the complete bipartite graph K_{2,4} is at least 4.
Read back from the Lean
Let $V$ and $W$ be finite types, and let $m, s \in \mathbb{N}$ such that $m \ge 2$, $|V| = m$, and $|W| = m$. Let $H$ be a simple graph on the vertex set $V \oplus W$ that is a subgraph of the complete bipartite graph between $V$ and $W$ ($H \le \mathrm{completeBipartiteGraph}\ V\ W$). Suppose $H$ is regular of degree $s$. Let $G = \mathrm{completeBipartiteGraph}\ V\ W \setminus H$ be the bipartite complement of $H$. Then: 1. $G$ is regular of degree $m - s$; 2. There exists a multiset $M$ of real numbers such that: - the cardinality of $M$ is $2m - 2$, - the multiset of roots of the characteristic polynomial of the adjacency matrix of $H$ over $\mathbb{R}$ is $\{s, -s\} + M$, and - the multiset of roots of the characteristic polynomial of the adjacency matrix of $G$ over $\mathbb{R}$ is $\{m - s, -(m - s)\} + M$; 3. If $2s < m$, then: - $G$ is connected, and - $\mathrm{adjacency\_lambda2}(G) = \mathrm{adjacency\_lambda2}(H)$.
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
Proof sketch. The bipartite complement G = K_{m,m} \ H is (m - s)-regular by degree subtraction. Using an algebraic identity relating the characteristic polynomials of G and H, the spectra of H and G differ only in that the trivial eigenvalues {s, -s} of H are replaced by {m - s, -(m - s)} in G, while the remaining multiset M of 2m - 2 eigenvalues is shared. When 2s < m, G is connected, and the Perron–Frobenius bound |y| ≤ s on all y ∈ M guarantees that the maximum element x of M is strictly below the principal eigenvalue m - s of G and at most s for H. Consequently, x serves as the second largest eigenvalue of both graphs, showing λ₂(G) = λ₂(H).
G is (m - s)-regular, its characteristic polynomial satisfies charpoly(G) * (X^2 - s^2) = charpoly(H) * (X^2 - (m - s)^2), and the spectrum of H contains s and -s.
We introduce G = K_{V,W} \ H and invoke three prior results: the bipartite complement of an s-regular subgraph of K_{m,m} is (m - s)-regular (bipartite_complement_regular), their characteristic polynomials satisfy the stated identity (bipartite_complement_adj_charpoly_mul), and the spectrum of any regular bipartite graph contains ± its degree (regular_bipartite_adj_charpoly_roots_contain_pm_degree).
uses
bipartite_complement_regular,bipartite_complement_adj_charpoly_mul,regular_bipartite_adj_charpoly_roots_contain_pm_degreeintro G have hreg := bipartite_complement_regular m s hV hW H hH_sub hH_reg have hid := bipartite_complement_adj_charpoly_mul m s hV hW H hH_sub hH_reg have hB := regular_bipartite_adj_charpoly_roots_contain_pm_degree m s (by omega) hV hW H hH_sub hH_reg
s ≤ m.
Because m ≥ 2, V is non-empty. Picking any vertex v₀ ∈ V, its degree in H is s by regularity. Since H is a subgraph of the complete bipartite graph K_{V,W}, all neighbors of v₀ lie in W. Therefore, s = deg(v₀) ≤ |W| = m.
uses
Fintype.card_pos_iff,SimpleGraph.mem_neighborFinset,Finset.card_le_card,Finset.card_map,Finset.card_univhave hsm : s ≤ m := by obtain ⟨v0⟩ : Nonempty V := by rw [← Fintype.card_pos_iff]; omega have h1 : H.degree (Sum.inl v0) = s := hH_reg _ have h2 : H.neighborFinset (Sum.inl v0) ⊆ Finset.univ.map Function.Embedding.inr := by intro x hx rw [SimpleGraph.mem_neighborFinset] at hx have := hH_sub hx rcases x with v | w · simp at this · simp have := Finset.card_le_card h2 rw [Finset.card_map, Finset.card_univ, hW] at this rw [← h1]; exact this
The adjacency matrix of H has 2m eigenvalues (roots of its characteristic polynomial, counting multiplicity).
The adjacency matrix of H is real symmetric (Hermitian) of dimension |V ⊕ W| = m + m = 2m, so all its eigenvalues are real and the characteristic polynomial has exactly 2m roots with multiplicity.
have hcardH : Multiset.card (H.adjMatrix ℝ).charpoly.roots = 2 * m := by rw [(H.isHermitian_adjMatrix ℝ).roots_charpoly_eq_eigenvalues] simp [hV, hW]; ring
For every real c, the multiset of roots of X^2 - c^2 is {c, -c}.
Factoring X^2 - c^2 = (X - c)(X + c) into monic linear factors over ℝ expresses its root multiset as the sum of the roots {c} of X - c and {-c} of X + c.
uses
Polynomial.roots_mul,Polynomial.roots_X_sub_Chave hroots2 : ∀ c : ℝ, (Polynomial.X ^ 2 - Polynomial.C (c ^ 2) : Polynomial ℝ).roots = {c, -c} := by intro c have : (Polynomial.X ^ 2 - Polynomial.C (c ^ 2) : Polynomial ℝ) = (Polynomial.X - Polynomial.C c) * (Polynomial.X - Polynomial.C (-c)) := by rw [Polynomial.C_neg, map_pow]; ring rw [this, Polynomial.roots_mul ((Polynomial.monic_X_sub_C c).mul (Polynomial.monic_X_sub_C _)).ne_zero, Polynomial.roots_X_sub_C, Polynomial.roots_X_sub_C] rfl
The root multisets satisfy roots(charpoly(G)) + {s, -s} = roots(charpoly(H)) + {m - s, -(m - s)}.
Taking roots on both sides of the polynomial identity charpoly(G) * (X^2 - s^2) = charpoly(H) * (X^2 - (m - s)^2), applying the property that the roots of a product of non-zero polynomials is the sum of their root multisets (Polynomial.roots_mul), and substituting the roots of X^2 - s^2 and X^2 - (m - s)^2.
uses
Polynomial.roots_mulhave hsum : (G.adjMatrix ℝ).charpoly.roots + {(s : ℝ), -(s : ℝ)} = (H.adjMatrix ℝ).charpoly.roots + {((m : ℝ) - s), -((m : ℝ) - s)} := by have := congrArg Polynomial.roots hid rw [Polynomial.roots_mul, Polynomial.roots_mul, hroots2, hroots2] at this · exact this · exact ((Matrix.charpoly_monic _).mul (Polynomial.monic_X_pow_sub_C _ (by norm_num))).ne_zero · exact ((Matrix.charpoly_monic _).mul (Polynomial.monic_X_pow_sub_C _ (by norm_num))).ne_zero
Setting M = roots(charpoly(H)) \ {s, -s}, M has cardinality 2m - 2, the eigenvalues of H are {s, -s} + M, and those of G are {m - s, -(m - s)} + M.
Since {s, -s} is contained in the roots of H, removing them leaves a multiset M such that roots(H) = {s, -s} + M. Substituting this into the root sum identity and cancelling {s, -s} on both sides via add_right_cancel yields roots(G) = {m - s, -(m - s)} + M. Comparing cardinalities shows |M| = 2m - 2. This discharges the regularity and spectrum statements of the theorem.
uses
add_tsub_cancel_of_le,Nat.cast_sub,add_right_cancel,Multiset.card_addset M := (H.adjMatrix ℝ).charpoly.roots - {(s : ℝ), -(s : ℝ)} with hMdef have hHM : (H.adjMatrix ℝ).charpoly.roots = {(s : ℝ), -(s : ℝ)} + M := (add_tsub_cancel_of_le hB).symm have hGM : (G.adjMatrix ℝ).charpoly.roots = {((m - s : ℕ) : ℝ), -((m - s : ℕ) : ℝ)} + M := by rw [Nat.cast_sub hsm] have : (G.adjMatrix ℝ).charpoly.roots + {(s : ℝ), -(s : ℝ)} = ({((m : ℝ) - s), -((m : ℝ) - s)} + M) + {(s : ℝ), -(s : ℝ)} := by rw [hsum, hHM]; abel exact add_right_cancel this have hcardM : Multiset.card M = 2 * m - 2 := by have := congrArg Multiset.card hHM rw [hcardH, Multiset.card_add] at this simp at this omega refine ⟨hreg, ⟨M, hcardM, hHM, hGM⟩, ?_⟩
Assuming 2s < m, the bipartite complement G is connected.
By bipartite_complement_connected, any bipartite complement of an s-regular subgraph of K_{m,m} with m ≥ 2 and 2s < m is connected.
uses
bipartite_complement_connectedintro hs2 refine ⟨bipartite_complement_connected m s hm hV hW H hH_sub hH_reg hs2, ?_⟩
The multiset M is non-empty and has a maximum element x.
Since m ≥ 2, the cardinality |M| = 2m - 2 is at least 2, so M is non-empty. Every non-empty finite multiset of reals contains a maximum element x, so y ≤ x for all y ∈ M.
uses
Multiset.mem_toFinsethave hMne : M ≠ 0 := by intro h rw [h] at hcardM simp at hcardM omega obtain ⟨x, hxM, hxmax⟩ := M.toFinset.exists_max_image id (Multiset.toFinset_nonempty.mpr hMne) rw [Multiset.mem_toFinset] at hxM replace hxmax : ∀ y ∈ M, y ≤ x := fun y hy => hxmax y (Multiset.mem_toFinset.mpr hy)
The maximum element x satisfies -s ≤ x ≤ s < m - s.
Every eigenvalue y ∈ M of H satisfies |y| ≤ s by the Perron–Frobenius bound for regular graphs (regular_adj_charpoly_root_abs_le). In particular, |x| ≤ s, which implies -s ≤ x ≤ s. Combining this with 2s < m gives s < m - s.
uses
regular_adj_charpoly_root_abs_le,abs_le.mphave habs : ∀ y ∈ M, |y| ≤ s := by intro y hy have hy' : y ∈ (H.adjMatrix ℝ).charpoly.roots := by rw [hHM]; exact Multiset.mem_add.mpr (Or.inr hy) exact regular_adj_charpoly_root_abs_le H s hH_reg y (by convert hy') have hx := abs_le.mp (habs x hxM) have hM' := Multiset.cons_erase hxM have hsm' : (s : ℝ) < ((m - s : ℕ) : ℝ) := by rw [Nat.cast_sub hsm] have : (2 * s : ℝ) < m := by exact_mod_cast hs2 linarith
The root multisets of H and G can be written as s :: x :: ((-s) :: M \ {x}) and (m - s) :: x :: (-(m - s) :: M \ {x}), respectively.
Decomposing M = {x} + (M \ {x}) and rearranging the multiset sums places the trivial positive eigenvalue first, x second, and the remaining eigenvalues thereafter.
have hHr : (H.adjMatrix ℝ).charpoly.roots = (s : ℝ) ::ₘ x ::ₘ (-(s : ℝ) ::ₘ M.erase x) := by rw [hHM] conv_lhs => rw [← hM'] simp only [Multiset.insert_eq_cons, ← Multiset.singleton_add] abel have hGr : (G.adjMatrix ℝ).charpoly.roots = ((m - s : ℕ) : ℝ) ::ₘ x ::ₘ (-((m - s : ℕ) : ℝ) ::ₘ M.erase x) := by rw [hGM] conv_lhs => rw [← hM'] simp only [Multiset.insert_eq_cons, ← Multiset.singleton_add] abel
The second largest eigenvalue λ₂(H) equals x.
We apply adjacency_lambda2_eq_of_charpoly_roots: the leading eigenvalue of H is s, x ≤ s, and every remaining eigenvalue is either -s ≤ x or an element y ∈ M \ {x} with y ≤ x by maximality of x. Thus λ₂(H) = x.
uses
adjacency_lambda2_eq_of_charpoly_roots,Multiset.mem_of_mem_erasehave hlamH : adjacency_lambda2 H = x := by apply adjacency_lambda2_eq_of_charpoly_roots H s x (-(s : ℝ) ::ₘ M.erase x) · convert hHr · exact hx.2 · intro y hy rcases Multiset.mem_cons.mp hy with rfl | hy · exact hx.1 · exact hxmax y (Multiset.mem_of_mem_erase hy)
The second largest eigenvalue λ₂(G) equals x, and therefore λ₂(G) = λ₂(H).
Applying adjacency_lambda2_eq_of_charpoly_roots to G, the leading eigenvalue is m - s, x < m - s, and all other eigenvalues are either -(m - s) < -s ≤ x or y ∈ M \ {x} with y ≤ x. Thus λ₂(G) = x, which equals λ₂(H).
uses
adjacency_lambda2_eq_of_charpoly_roots,Multiset.mem_of_mem_erasehave hlamG : adjacency_lambda2 G = x := by apply adjacency_lambda2_eq_of_charpoly_roots G ((m - s : ℕ) : ℝ) x (-((m - s : ℕ) : ℝ) ::ₘ M.erase x) · convert hGr · linarith [hx.2] · intro y hy rcases Multiset.mem_cons.mp hy with rfl | hy · linarith [hx.1] · exact hxmax y (Multiset.mem_of_mem_erase hy) rw [hlamG, hlamH]
bipartite_complement_regular- The bipartite complement of an s-regular subgraph of K_{m,m} is (m - s)-regular.
bipartite_complement_adj_charpoly_mul- For an s-regular subgraph H ≤ K_{m,m} and its bipartite complement G, charpoly(G) * (X^2 - s^2) = charpoly(H) * (X^2 - (m - s)^2).
regular_bipartite_adj_charpoly_roots_contain_pm_degree- The multiset of eigenvalues of any s-regular bipartite graph with parts of size m ≥ 1 contains s and -s.
Fintype.card_pos_iff- A finite type has positive cardinality if and only if it is non-empty.
SimpleGraph.mem_neighborFinset- A vertex w belongs to the neighbor finset of v if and only if v and w are adjacent in the graph.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most that of the other.
Finset.card_map- Mapping an injective function over a finite set preserves its cardinality.
Finset.card_univ- The cardinality of the universe finset of a finite type equals the cardinality of the type.
Polynomial.roots_mul- The multiset of roots of the product of two non-zero polynomials is the sum of their root multisets.
Polynomial.roots_X_sub_C- The monic linear polynomial X - r has the single root r.
add_tsub_cancel_of_le- Subtracting a submultiset a ≤ b and adding it back recovers b, so a + (b - a) = b.
Nat.cast_sub- For natural numbers with s ≤ m, the real cast of m - s equals the real difference m - s.
add_right_cancel- In an additive structure with right cancellation, a + b = c + b implies a = c.
Multiset.card_add- The cardinality of the sum of two multisets is the sum of their cardinalities.
bipartite_complement_connected- The bipartite complement of an s-regular subgraph of K_{m,m} is connected whenever 2s < m and m ≥ 2.
Multiset.mem_toFinset- An element belongs to the finset of elements of a multiset if and only if it belongs to the multiset.
regular_adj_charpoly_root_abs_le- Every eigenvalue of the adjacency matrix of an s-regular graph has absolute value at most s.
abs_le.mp- An inequality |a| ≤ b implies -b ≤ a and a ≤ b.
adjacency_lambda2_eq_of_charpoly_roots- If the eigenvalues of a graph consist of a, x, and a multiset M where x ≤ a and every element of M is at most x, then the second largest eigenvalue λ₂ equals x.
Multiset.mem_of_mem_erase- If an element belongs to the multiset obtained by erasing an occurrence of a value, it belonged to the original multiset.
- The root multiset rearrangements (lines 88–98) and root multiset subtraction (lines 52–65) are formal bookkeeping steps required by Lean's constructive representation of multisets and lists of roots, corresponding on paper to cancelling common polynomial factors and sorting eigenvalues.
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.
open scoped Classical intheorem bipartite_complement_adj_spectrum_and_lambda2 {V W : Type*} [Fintype V] [Fintype W] (m s : ℕ) (hm : 2 ≤ m) (hV : Fintype.card V = m) (hW : Fintype.card W = m) (H : SimpleGraph (V ⊕ W)) (hH_sub : H ≤ completeBipartiteGraph V W) (hH_reg : H.IsRegularOfDegree s) : let G := completeBipartiteGraph V W \ H G.IsRegularOfDegree (m - s) ∧ (∃ M : Multiset ℝ, Multiset.card M = 2 * m - 2 ∧ (H.adjMatrix ℝ).charpoly.roots = {(s : ℝ), -(s : ℝ)} + M ∧ (G.adjMatrix ℝ).charpoly.roots = {((m - s : ℕ) : ℝ), -((m - s : ℕ) : ℝ)} + M) ∧ (2 * s < m → G.Connected ∧ adjacency_lambda2 G = adjacency_lambda2 H) := by intro G have hreg := bipartite_complement_regular m s hV hW H hH_sub hH_reg have hid := bipartite_complement_adj_charpoly_mul m s hV hW H hH_sub hH_reg have hB := regular_bipartite_adj_charpoly_roots_contain_pm_degree m s (by omega) hV hW H hH_sub hH_reg have hsm : s ≤ m := by obtain ⟨v0⟩ : Nonempty V := by rw [← Fintype.card_pos_iff]; omega have h1 : H.degree (Sum.inl v0) = s := hH_reg _ have h2 : H.neighborFinset (Sum.inl v0) ⊆ Finset.univ.map Function.Embedding.inr := by intro x hx rw [SimpleGraph.mem_neighborFinset] at hx have := hH_sub hx rcases x with v | w · simp at this · simp have := Finset.card_le_card h2 rw [Finset.card_map, Finset.card_univ, hW] at this rw [← h1]; exact this have hcardH : Multiset.card (H.adjMatrix ℝ).charpoly.roots = 2 * m := by rw [(H.isHermitian_adjMatrix ℝ).roots_charpoly_eq_eigenvalues] simp [hV, hW]; ring have hroots2 : ∀ c : ℝ, (Polynomial.X ^ 2 - Polynomial.C (c ^ 2) : Polynomial ℝ).roots = {c, -c} := by intro c have : (Polynomial.X ^ 2 - Polynomial.C (c ^ 2) : Polynomial ℝ) = (Polynomial.X - Polynomial.C c) * (Polynomial.X - Polynomial.C (-c)) := by rw [Polynomial.C_neg, map_pow]; ring rw [this, Polynomial.roots_mul ((Polynomial.monic_X_sub_C c).mul (Polynomial.monic_X_sub_C _)).ne_zero, Polynomial.roots_X_sub_C, Polynomial.roots_X_sub_C] rfl have hsum : (G.adjMatrix ℝ).charpoly.roots + {(s : ℝ), -(s : ℝ)} = (H.adjMatrix ℝ).charpoly.roots + {((m : ℝ) - s), -((m : ℝ) - s)} := by have := congrArg Polynomial.roots hid rw [Polynomial.roots_mul, Polynomial.roots_mul, hroots2, hroots2] at this · exact this · exact ((Matrix.charpoly_monic _).mul (Polynomial.monic_X_pow_sub_C _ (by norm_num))).ne_zero · exact ((Matrix.charpoly_monic _).mul (Polynomial.monic_X_pow_sub_C _ (by norm_num))).ne_zero set M := (H.adjMatrix ℝ).charpoly.roots - {(s : ℝ), -(s : ℝ)} with hMdef have hHM : (H.adjMatrix ℝ).charpoly.roots = {(s : ℝ), -(s : ℝ)} + M := (add_tsub_cancel_of_le hB).symm have hGM : (G.adjMatrix ℝ).charpoly.roots = {((m - s : ℕ) : ℝ), -((m - s : ℕ) : ℝ)} + M := by rw [Nat.cast_sub hsm] have : (G.adjMatrix ℝ).charpoly.roots + {(s : ℝ), -(s : ℝ)} = ({((m : ℝ) - s), -((m : ℝ) - s)} + M) + {(s : ℝ), -(s : ℝ)} := by rw [hsum, hHM]; abel exact add_right_cancel this have hcardM : Multiset.card M = 2 * m - 2 := by have := congrArg Multiset.card hHM rw [hcardH, Multiset.card_add] at this simp at this omega refine ⟨hreg, ⟨M, hcardM, hHM, hGM⟩, ?_⟩ intro hs2 refine ⟨bipartite_complement_connected m s hm hV hW H hH_sub hH_reg hs2, ?_⟩ have hMne : M ≠ 0 := by intro h rw [h] at hcardM simp at hcardM omega obtain ⟨x, hxM, hxmax⟩ := M.toFinset.exists_max_image id (Multiset.toFinset_nonempty.mpr hMne) rw [Multiset.mem_toFinset] at hxM replace hxmax : ∀ y ∈ M, y ≤ x := fun y hy => hxmax y (Multiset.mem_toFinset.mpr hy) have habs : ∀ y ∈ M, |y| ≤ s := by intro y hy have hy' : y ∈ (H.adjMatrix ℝ).charpoly.roots := by rw [hHM]; exact Multiset.mem_add.mpr (Or.inr hy) exact regular_adj_charpoly_root_abs_le H s hH_reg y (by convert hy') have hx := abs_le.mp (habs x hxM) have hM' := Multiset.cons_erase hxM have hsm' : (s : ℝ) < ((m - s : ℕ) : ℝ) := by rw [Nat.cast_sub hsm] have : (2 * s : ℝ) < m := by exact_mod_cast hs2 linarith have hHr : (H.adjMatrix ℝ).charpoly.roots = (s : ℝ) ::ₘ x ::ₘ (-(s : ℝ) ::ₘ M.erase x) := by rw [hHM] conv_lhs => rw [← hM'] simp only [Multiset.insert_eq_cons, ← Multiset.singleton_add] abel have hGr : (G.adjMatrix ℝ).charpoly.roots = ((m - s : ℕ) : ℝ) ::ₘ x ::ₘ (-((m - s : ℕ) : ℝ) ::ₘ M.erase x) := by rw [hGM] conv_lhs => rw [← hM'] simp only [Multiset.insert_eq_cons, ← Multiset.singleton_add] abel have hlamH : adjacency_lambda2 H = x := by apply adjacency_lambda2_eq_of_charpoly_roots H s x (-(s : ℝ) ::ₘ M.erase x) · convert hHr · exact hx.2 · intro y hy rcases Multiset.mem_cons.mp hy with rfl | hy · exact hx.1 · exact hxmax y (Multiset.mem_of_mem_erase hy) have hlamG : adjacency_lambda2 G = x := by apply adjacency_lambda2_eq_of_charpoly_roots G ((m - s : ℕ) : ℝ) x (-((m - s : ℕ) : ℝ) ::ₘ M.erase x) · convert hGr · linarith [hx.2] · intro y hy rcases Multiset.mem_cons.mp hy with rfl | hy · linarith [hx.1] · exact hxmax y (Multiset.mem_of_mem_erase hy) rw [hlamG, hlamH]