icosahedron_is_amply_regular
The icosahedron graph on Fin 12 is an amply regular graph with parameters (5, 2, 2) and its diameter is 3.
Statement
theorem icosahedron_is_amply_regular [DecidableRel icosahedron_graph.Adj] :
IsAmplyRegular icosahedron_graph 5 2 2 ∧
icosahedron_graph.diam = 3- Source
- arXiv:2610.36620, Proof of Theorem 3.6
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- icosahedron_graphThe simple graph on Fin 12 defined via SimpleGraph.fromRel with antipodal vertices 0 and 11: vertex 0 is adjacent to vertices 1 through 5,…
- IsAmplyRegularA graph G on a finite vertex set is amply regular with parameters (k, ℓ, μ) if it is regular of degree k, every pair of adjacent vertices…
Read back from the Lean
Assuming adjacency in icosahedron_graph is decidable, the graph icosahedron_graph is amply regular with parameters $k = 5$, $\ell = 2$, and $\mu = 2$, and its graph diameter is equal to $3$.
That is:
1. Every vertex in icosahedron_graph has degree $5$;
2. For every pair of adjacent vertices $u, v$, the number of common neighbors of $u$ and $v$ is $2$;
3. For every pair of vertices $u, v$ at graph distance $2$ (i.e., icosahedron_graph.dist u v = 2), the number of common neighbors of $u$ and $v$ is $2$;
4. The diameter of icosahedron_graph (icosahedron_graph.diam) is $3$.
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 theorem establishes that the icosahedron graph on 12 vertices is an amply regular graph with parameters (5, 2, 2) and has diameter 3. The proof proceeds by verifying the regularity, common neighbor counts, and diameter through finite computation and explicit distance bounds.
The icosahedron graph is amply regular with parameters (5, 2, 2) and diameter 3.
Full proof.
simp [icosahedron_is_amply_regular_adj, icosahedron_graph, SimpleGraph.fromRel, decide_eq_true_eq] lemma icosahedron_is_amply_regular_nbr_mem (v w : Fin 12) : w ∈ icosahedron_is_amply_regular_nbr v ↔ icosahedron_graph.Adj v w := by simp [icosahedron_is_amply_regular_nbr, icosahedron_is_amply_regular_adj_iff] lemma icosahedron_is_amply_regular_nbr_card (v : Fin 12) : (icosahedron_is_amply_regular_nbr v).card = 5 := by decide +revert lemma icosahedron_is_amply_regular_card_adj (u v : Fin 12) (h : icosahedron_is_amply_regular_adj u v = true) : (icosahedron_is_amply_regular_nbr u ∩ icosahedron_is_amply_regular_nbr v).card = 2 := by have h' : ∀ a b : Fin 12, icosahedron_is_amply_regular_adj a b = true → (icosahedron_is_amply_regular_nbr a ∩ icosahedron_is_amply_regular_nbr b).card = 2 := by decide exact h' u v h lemma icosahedron_is_amply_regular_card_dist_two (u v : Fin 12) (hne : u ≠ v) (hn : (icosahedron_is_amply_regular_nbr u ∩ icosahedron_is_amply_regular_nbr v).Nonempty) : (icosahedron_is_amply_regular_nbr u ∩ icosahedron_is_amply_regular_nbr v).card = 2 := by have h' : ∀ a b : Fin 12, a ≠ b → (icosahedron_is_amply_regular_nbr a ∩ icosahedron_is_amply_regular_nbr b).Nonempty → (icosahedron_is_amply_regular_nbr a ∩ icosahedron_is_amply_regular_nbr b).card = 2 := by decide exact h' u v hne hn abbrev icosahedron_is_amply_regular_within_three (u v : Fin 12) : Prop := u = v ∨ icosahedron_is_amply_regular_adj u v = true ∨ (∃ w, icosahedron_is_amply_regular_adj u w = true ∧ icosahedron_is_amply_regular_adj w v = true) ∨ (∃ w x, icosahedron_is_amply_regular_adj u w = true ∧ icosahedron_is_amply_regular_adj w x = true ∧ icosahedron_is_amply_regular_adj x v = true) lemma icosahedron_is_amply_regular_within_three_all : ∀ u v : Fin 12, icosahedron_is_amply_regular_within_three u v := by decide lemma icosahedron_is_amply_regular_edist_le_three (u v : Fin 12) : icosahedron_graph.edist u v ≤ (3 : ℕ∞) := by rcases icosahedron_is_amply_regular_within_three_all u v with h | h | ⟨w, h1, h2⟩ | ⟨w, x, h1, h2, h3⟩ · subst h; simp · have hadj : icosahedron_graph.Adj u v := (icosahedron_is_amply_regular_adj_iff u v).2 h rw [SimpleGraph.edist_eq_one_iff_adj.mpr hadj] norm_num · have h1' : icosahedron_graph.Adj u w := (icosahedron_is_amply_regular_adj_iff u w).2 h1 have h2' : icosahedron_graph.Adj w v := (icosahedron_is_amply_regular_adj_iff w v).2 h2 have hp := SimpleGraph.edist_le (SimpleGraph.Walk.cons h1' (SimpleGraph.Walk.cons h2' SimpleGraph.Walk.nil) : icosahedron_graph.Walk u v) have h2le : icosahedron_graph.edist u v ≤ (2 : ℕ∞) := by simpa using hp exact h2le.trans (by norm_num) · have h1' : icosahedron_graph.Adj u w := (icosahedron_is_amply_regular_adj_iff u w).2 h1 have h2' : icosahedron_graph.Adj w x := (icosahedron_is_amply_regular_adj_iff w x).2 h2 have h3' : icosahedron_graph.Adj x v := (icosahedron_is_amply_regular_adj_iff x v).2 h3 have hp := SimpleGraph.edist_le (SimpleGraph.Walk.cons h1' (SimpleGraph.Walk.cons h2' (SimpleGraph.Walk.cons h3' SimpleGraph.Walk.nil)) : icosahedron_graph.Walk u v) simpa using hp lemma icosahedron_is_amply_regular_ediam_le_three : icosahedron_graph.ediam ≤ (3 : ℕ∞) := by rw [SimpleGraph.ediam_le_iff] exact icosahedron_is_amply_regular_edist_le_three lemma icosahedron_is_amply_regular_ediam_ne_top : icosahedron_graph.ediam ≠ ⊤ := by have h := icosahedron_is_amply_regular_ediam_le_three intro htop rw [htop] at h exact absurd h (by simp) lemma icosahedron_is_amply_regular_diam_le_three : icosahedron_graph.diam ≤ 3 := by simp only [SimpleGraph.diam] have := ENat.toNat_le_toNat (m := icosahedron_graph.ediam) (n := 3) icosahedron_is_amply_regular_ediam_le_three (by simp) simpa using this lemma icosahedron_is_amply_regular_common_0_11 : icosahedron_graph.commonNeighbors 0 11 = ∅ := by have h0 : icosahedron_is_amply_regular_nbr 0 ∩ icosahedron_is_amply_regular_nbr 11 = ∅ := by decide rw [Set.eq_empty_iff_forall_notMem] intro x hx rw [SimpleGraph.mem_commonNeighbors] at hx have hmem : x ∈ icosahedron_is_amply_regular_nbr 0 ∩ icosahedron_is_amply_regular_nbr 11 := by simp only [Finset.mem_inter, icosahedron_is_amply_regular_nbr_mem] exact hx rw [h0] at hmem exact Finset.notMem_empty x hmem lemma icosahedron_is_amply_regular_two_lt_edist_0_11 : (2 : ℕ∞) < icosahedron_graph.edist 0 11 := by rw [SimpleGraph.two_lt_edist_iff] refine ⟨by decide, ?_, icosahedron_is_amply_regular_common_0_11⟩ rw [icosahedron_is_amply_regular_adj_iff] decide lemma icosahedron_is_amply_regular_nbr_eq [DecidableRel icosahedron_graph.Adj] (v : Fin 12) : icosahedron_graph.neighborFinset v = icosahedron_is_amply_regular_nbr v := by ext w simp [SimpleGraph.mem_neighborFinset, icosahedron_is_amply_regular_nbr_mem] lemma icosahedron_is_amply_regular_card_common [DecidableRel icosahedron_graph.Adj] (u v : Fin 12) : Fintype.card ↑(icosahedron_graph.commonNeighbors u v) = (icosahedron_is_amply_regular_nbr u ∩ icosahedron_is_amply_regular_nbr v).card := by rw [Fintype.card_subtype (fun x => x ∈ icosahedron_graph.commonNeighbors u v)] congr 1 ext x simp [Finset.mem_inter, icosahedron_is_amply_regular_nbr_mem, SimpleGraph.mem_commonNeighbors] lemma icosahedron_is_amply_regular_diam_ge_three : 3 ≤ icosahedron_graph.diam := by have h3 : (3 : ℕ∞) ≤ icosahedron_graph.ediam := (Order.add_one_le_of_lt icosahedron_is_amply_regular_two_lt_edist_0_11).trans SimpleGraph.edist_le_ediam simp only [SimpleGraph.diam] have := ENat.toNat_le_toNat h3 icosahedron_is_amply_regular_ediam_ne_top simpa using this /-- The icosahedron graph is amply regular with parameters (5, 2, 2) and has diameter 3. -/ theorem icosahedron_is_amply_regular [DecidableRel icosahedron_graph.Adj] : IsAmplyRegular icosahedron_graph 5 2 2 ∧ icosahedron_graph.diam = 3 := by refine ⟨⟨?_, ?_, ?_⟩, ?_⟩ · intro v show (icosahedron_graph.neighborFinset v).card = 5 rw [icosahedron_is_amply_regular_nbr_eq, icosahedron_is_amply_regular_nbr_card] · intro u v huv rw [icosahedron_is_amply_regular_card_common, icosahedron_is_amply_regular_card_adj u v ((icosahedron_is_amply_regular_adj_iff u v).1 huv)] · intro u v h have hne0 : icosahedron_graph.dist u v ≠ 0 := by omega obtain ⟨huv, hreach⟩ := SimpleGraph.dist_ne_zero_iff_ne_and_reachable.1 hne0 have hed : icosahedron_graph.edist u v = (2 : ℕ∞) := by rw [← hreach.coe_dist_eq_edist, h] norm_num obtain ⟨hne, -, hnonempty⟩ := SimpleGraph.edist_eq_two_iff.1 hed rw [icosahedron_is_amply_regular_card_common] refine icosahedron_is_amply_regular_card_dist_two u v hne ?_ obtain ⟨x, hx⟩ := hnonempty rw [SimpleGraph.mem_commonNeighbors] at hx exact ⟨x, by simp only [Finset.mem_inter, icosahedron_is_amply_regular_nbr_mem]; exact hx⟩ · exact le_antisymm icosahedron_is_amply_regular_diam_le_three icosahedron_is_amply_regular_diam_ge_three
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.
abbrev icosahedron_is_amply_regular_rel (x y : ℕ) : Prop := (x = 0 ∧ 1 ≤ y ∧ y ≤ 5) ∨ (x = 11 ∧ 6 ≤ y ∧ y ≤ 10) ∨ (1 ≤ x ∧ x ≤ 5 ∧ 1 ≤ y ∧ y ≤ 5 ∧ (y = x % 5 + 1 ∨ x = y % 5 + 1)) ∨ (6 ≤ x ∧ x ≤ 10 ∧ 6 ≤ y ∧ y ≤ 10 ∧ (y = 6 + (x - 6 + 1) % 5 ∨ x = 6 + (y - 6 + 1) % 5)) ∨ (1 ≤ x ∧ x ≤ 5 ∧ 6 ≤ y ∧ y ≤ 10 ∧ (y = 6 + (x - 1) ∨ y = 6 + (x - 1 + 4) % 5))def icosahedron_is_amply_regular_adj (u v : Fin 12) : Bool := decide (u ≠ v ∧ (icosahedron_is_amply_regular_rel u.val v.val ∨ icosahedron_is_amply_regular_rel v.val u.val))def icosahedron_is_amply_regular_nbr (v : Fin 12) : Finset (Fin 12) := Finset.univ.filter (fun w => icosahedron_is_amply_regular_adj v w)lemma icosahedron_is_amply_regular_adj_iff (u v : Fin 12) : icosahedron_graph.Adj u v ↔ icosahedron_is_amply_regular_adj u v = true := by simp [icosahedron_is_amply_regular_adj, icosahedron_graph, SimpleGraph.fromRel, decide_eq_true_eq]lemma icosahedron_is_amply_regular_nbr_mem (v w : Fin 12) : w ∈ icosahedron_is_amply_regular_nbr v ↔ icosahedron_graph.Adj v w := by simp [icosahedron_is_amply_regular_nbr, icosahedron_is_amply_regular_adj_iff]lemma icosahedron_is_amply_regular_nbr_card (v : Fin 12) : (icosahedron_is_amply_regular_nbr v).card = 5 := by decide +revertlemma icosahedron_is_amply_regular_card_adj (u v : Fin 12) (h : icosahedron_is_amply_regular_adj u v = true) : (icosahedron_is_amply_regular_nbr u ∩ icosahedron_is_amply_regular_nbr v).card = 2 := by have h' : ∀ a b : Fin 12, icosahedron_is_amply_regular_adj a b = true → (icosahedron_is_amply_regular_nbr a ∩ icosahedron_is_amply_regular_nbr b).card = 2 := by decide exact h' u v hlemma icosahedron_is_amply_regular_card_dist_two (u v : Fin 12) (hne : u ≠ v) (hn : (icosahedron_is_amply_regular_nbr u ∩ icosahedron_is_amply_regular_nbr v).Nonempty) : (icosahedron_is_amply_regular_nbr u ∩ icosahedron_is_amply_regular_nbr v).card = 2 := by have h' : ∀ a b : Fin 12, a ≠ b → (icosahedron_is_amply_regular_nbr a ∩ icosahedron_is_amply_regular_nbr b).Nonempty → (icosahedron_is_amply_regular_nbr a ∩ icosahedron_is_amply_regular_nbr b).card = 2 := by decide exact h' u v hne hnabbrev icosahedron_is_amply_regular_within_three (u v : Fin 12) : Prop := u = v ∨ icosahedron_is_amply_regular_adj u v = true ∨ (∃ w, icosahedron_is_amply_regular_adj u w = true ∧ icosahedron_is_amply_regular_adj w v = true) ∨ (∃ w x, icosahedron_is_amply_regular_adj u w = true ∧ icosahedron_is_amply_regular_adj w x = true ∧ icosahedron_is_amply_regular_adj x v = true)lemma icosahedron_is_amply_regular_within_three_all : ∀ u v : Fin 12, icosahedron_is_amply_regular_within_three u v := by decidelemma icosahedron_is_amply_regular_edist_le_three (u v : Fin 12) : icosahedron_graph.edist u v ≤ (3 : ℕ∞) := by rcases icosahedron_is_amply_regular_within_three_all u v with h | h | ⟨w, h1, h2⟩ | ⟨w, x, h1, h2, h3⟩ · subst h; simp · have hadj : icosahedron_graph.Adj u v := (icosahedron_is_amply_regular_adj_iff u v).2 h rw [SimpleGraph.edist_eq_one_iff_adj.mpr hadj] norm_num · have h1' : icosahedron_graph.Adj u w := (icosahedron_is_amply_regular_adj_iff u w).2 h1 have h2' : icosahedron_graph.Adj w v := (icosahedron_is_amply_regular_adj_iff w v).2 h2 have hp := SimpleGraph.edist_le (SimpleGraph.Walk.cons h1' (SimpleGraph.Walk.cons h2' SimpleGraph.Walk.nil) : icosahedron_graph.Walk u v) have h2le : icosahedron_graph.edist u v ≤ (2 : ℕ∞) := by simpa using hp exact h2le.trans (by norm_num) · have h1' : icosahedron_graph.Adj u w := (icosahedron_is_amply_regular_adj_iff u w).2 h1 have h2' : icosahedron_graph.Adj w x := (icosahedron_is_amply_regular_adj_iff w x).2 h2 have h3' : icosahedron_graph.Adj x v := (icosahedron_is_amply_regular_adj_iff x v).2 h3 have hp := SimpleGraph.edist_le (SimpleGraph.Walk.cons h1' (SimpleGraph.Walk.cons h2' (SimpleGraph.Walk.cons h3' SimpleGraph.Walk.nil)) : icosahedron_graph.Walk u v) simpa using hplemma icosahedron_is_amply_regular_ediam_le_three : icosahedron_graph.ediam ≤ (3 : ℕ∞) := by rw [SimpleGraph.ediam_le_iff] exact icosahedron_is_amply_regular_edist_le_threelemma icosahedron_is_amply_regular_ediam_ne_top : icosahedron_graph.ediam ≠ ⊤ := by have h := icosahedron_is_amply_regular_ediam_le_three intro htop rw [htop] at h exact absurd h (by simp)lemma icosahedron_is_amply_regular_diam_le_three : icosahedron_graph.diam ≤ 3 := by simp only [SimpleGraph.diam] have := ENat.toNat_le_toNat (m := icosahedron_graph.ediam) (n := 3) icosahedron_is_amply_regular_ediam_le_three (by simp) simpa using thislemma icosahedron_is_amply_regular_common_0_11 : icosahedron_graph.commonNeighbors 0 11 = ∅ := by have h0 : icosahedron_is_amply_regular_nbr 0 ∩ icosahedron_is_amply_regular_nbr 11 = ∅ := by decide rw [Set.eq_empty_iff_forall_notMem] intro x hx rw [SimpleGraph.mem_commonNeighbors] at hx have hmem : x ∈ icosahedron_is_amply_regular_nbr 0 ∩ icosahedron_is_amply_regular_nbr 11 := by simp only [Finset.mem_inter, icosahedron_is_amply_regular_nbr_mem] exact hx rw [h0] at hmem exact Finset.notMem_empty x hmemlemma icosahedron_is_amply_regular_two_lt_edist_0_11 : (2 : ℕ∞) < icosahedron_graph.edist 0 11 := by rw [SimpleGraph.two_lt_edist_iff] refine ⟨by decide, ?_, icosahedron_is_amply_regular_common_0_11⟩ rw [icosahedron_is_amply_regular_adj_iff] decidelemma icosahedron_is_amply_regular_nbr_eq [DecidableRel icosahedron_graph.Adj] (v : Fin 12) : icosahedron_graph.neighborFinset v = icosahedron_is_amply_regular_nbr v := by ext w simp [SimpleGraph.mem_neighborFinset, icosahedron_is_amply_regular_nbr_mem]lemma icosahedron_is_amply_regular_card_common [DecidableRel icosahedron_graph.Adj] (u v : Fin 12) : Fintype.card ↑(icosahedron_graph.commonNeighbors u v) = (icosahedron_is_amply_regular_nbr u ∩ icosahedron_is_amply_regular_nbr v).card := by rw [Fintype.card_subtype (fun x => x ∈ icosahedron_graph.commonNeighbors u v)] congr 1 ext x simp [Finset.mem_inter, icosahedron_is_amply_regular_nbr_mem, SimpleGraph.mem_commonNeighbors]lemma icosahedron_is_amply_regular_diam_ge_three : 3 ≤ icosahedron_graph.diam := by have h3 : (3 : ℕ∞) ≤ icosahedron_graph.ediam := (Order.add_one_le_of_lt icosahedron_is_amply_regular_two_lt_edist_0_11).trans SimpleGraph.edist_le_ediam simp only [SimpleGraph.diam] have := ENat.toNat_le_toNat h3 icosahedron_is_amply_regular_ediam_ne_top simpa using this/-- The icosahedron graph is amply regular with parameters (5, 2, 2) and has diameter 3. -/theorem icosahedron_is_amply_regular [DecidableRel icosahedron_graph.Adj] : IsAmplyRegular icosahedron_graph 5 2 2 ∧ icosahedron_graph.diam = 3 := by refine ⟨⟨?_, ?_, ?_⟩, ?_⟩ · intro v show (icosahedron_graph.neighborFinset v).card = 5 rw [icosahedron_is_amply_regular_nbr_eq, icosahedron_is_amply_regular_nbr_card] · intro u v huv rw [icosahedron_is_amply_regular_card_common, icosahedron_is_amply_regular_card_adj u v ((icosahedron_is_amply_regular_adj_iff u v).1 huv)] · intro u v h have hne0 : icosahedron_graph.dist u v ≠ 0 := by omega obtain ⟨huv, hreach⟩ := SimpleGraph.dist_ne_zero_iff_ne_and_reachable.1 hne0 have hed : icosahedron_graph.edist u v = (2 : ℕ∞) := by rw [← hreach.coe_dist_eq_edist, h] norm_num obtain ⟨hne, -, hnonempty⟩ := SimpleGraph.edist_eq_two_iff.1 hed rw [icosahedron_is_amply_regular_card_common] refine icosahedron_is_amply_regular_card_dist_two u v hne ?_ obtain ⟨x, hx⟩ := hnonempty rw [SimpleGraph.mem_commonNeighbors] at hx exact ⟨x, by simp only [Finset.mem_inter, icosahedron_is_amply_regular_nbr_mem]; exact hx⟩ · exact le_antisymm icosahedron_is_amply_regular_diam_le_three icosahedron_is_amply_regular_diam_ge_three