complete_graphic_matroid_szf_realizable_of_le_five
For 1 ≤ n ≤ 5 the cycle matroid M(K_n) is SZF-realizable by some multigraph on E(K_n).
Statement
theorem complete_graphic_matroid_szf_realizable_of_le_five (n : ℕ) (h1 : 1 ≤ n) (h5 : n ≤ 5) :
complete_graphic_matroid_szf_realizable n- Formalizes
- arXiv:2611.15741 Proposition 4.4 (the paper's K_4, K_5 graphs are only in a figure; the witnesses here were found by search, experiment 27629)
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- complete_graphic_matroid_szf_realizableThe cycle matroid M(K_n) is SZF-realizable: there is a multigraph on the ground set E(K_n) (symmetric adjacency multiplicities μ, loops…
- SzfMultiForcedSkew zero forcing on a multigraph with adjacency multiplicities μ (μ u v = number of edges between u and v, μ u u = number of loops at u):…
- complete_graph_cycle_closureThe closure operator of the cycle matroid M(K_n), as a map on sets of edges of K_n. The ground set is the edge set of the complete graph…
- szf_multigraph_closureThe skew zero forcing closure scl(S) of a vertex set S in the multigraph with adjacency multiplicities μ: the set of vertices forced from…
- Arena.Reachable.transReachability is transitive.
- Used by 1
- complete_graphic_matroid_szf_realizable_iffFor every integer n ≥ 1, the cycle matroid M(K_n) of the complete graph K_n is SZF-realizable (some multigraph on E(K_n), loops and…
Read back from the Lean
For any natural number $n$ such that $1 \le n$ and $n \le 5$, the complete graphic matroid on $n$ vertices is standard zero-forcing (SZF) realizable (complete_graphic_matroid_szf_realizable n): that is, there exists a symmetric function $\mu$ assigning a natural number to each pair of edges of the complete graph $K_n$ on vertex set Fin n such that for every edge subset $S$, the SZF multigraph closure of $S$ under $\mu$ coincides with the cycle closure of $S$ in $K_n$.
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 cycle matroid M(K_n) is shown to be multigraph zero-forcing (SZF) realizable for 1 ≤ n ≤ 5. The argument first characterizes graphic cycle closure as the minimal operator closed under triangle transitivity, and derives a local criterion (`kn_szf_eq_of`) reducing realizability to cycle soundness of forcing steps and single-step triangle completion. It then formulates these conditions for symmetric 4-index tables (`kn_szf_realizable_of_table`), and finally proves realizability for each n ∈ {1, 2, 3, 4, 5} by evaluating explicit edge-bitmask tables via computational reflection in the Lean kernel (`decide +kernel`).
Any edge set S of K_n is contained in its cycle closure.
Take an edge e = {a, b} in S. In the subgraph induced by S, a and b are adjacent by definition of the induced graph (`SimpleGraph.fromEdgeSet_adj`), hence reachable from one another (`SimpleGraph.Adj.reachable`). Thus e belongs to the cycle closure of S.
uses
Sym2.ind,SimpleGraph.Adj.reachable,SimpleGraph.fromEdgeSet_adjtheorem kn_szf_cl_sub {n : ℕ} (S : Set (⊤ : SimpleGraph (Fin n)).edgeSet) : S ⊆ complete_graph_cycle_closure n S := by rintro ⟨e, he⟩ hS induction e using Sym2.ind with | h a b => refine ⟨a, b, rfl, SimpleGraph.Adj.reachable ?_⟩ rw [SimpleGraph.fromEdgeSet_adj] exact ⟨⟨_, hS, rfl⟩, by simpa using he⟩
The cycle closure satisfies triangle transitivity: if {a, b} and {b, c} belong to the cycle closure of S with a ≠ c, then {a, c} also belongs to it.
By definition of the cycle closure, {a, b} in the closure means a and b are connected by a path in the subgraph spanned by S, and {b, c} in the closure means b and c are connected. Concatenating these paths shows a and c are reachable from each other, placing {a, c} in the closure.
uses
Sym2.eq_iff.1theorem kn_szf_cl_tri {n : ℕ} (S : Set (⊤ : SimpleGraph (Fin n)).edgeSet) (a b c : Fin n) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) (h1 : (⟨s(a, b), by simpa using hab⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ complete_graph_cycle_closure n S) (h2 : (⟨s(b, c), by simpa using hbc⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ complete_graph_cycle_closure n S) : (⟨s(a, c), by simpa using hac⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ complete_graph_cycle_closure n S := by obtain ⟨x, y, hxy, r1⟩ := h1 obtain ⟨z, w, hzw, r2⟩ := h2 have r1' : (SimpleGraph.fromEdgeSet (Subtype.val '' S)).Reachable a b := by rcases Sym2.eq_iff.1 hxy with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact r1 · exact r1.symm have r2' : (SimpleGraph.fromEdgeSet (Subtype.val '' S)).Reachable b c := by rcases Sym2.eq_iff.1 hzw with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact r2 · exact r2.symm exact ⟨a, c, rfl, r1'.trans r2'⟩
The cycle closure of S is the least set containing S that is closed under triangle transitivity.
Let T contain S and be closed under triangle transitivity. Any edge {a, b} in the cycle closure of S corresponds to a path connecting a and b in S. By induction on the length of this path using the reflexive-transitive closure of adjacency (`SimpleGraph.reachable_iff_reflTransGen`), each edge along the path is in S ⊆ T, and repeated triangle transitivity shows that every intermediate vertex c satisfies {a, c} ∈ T, so {a, b} ∈ T.
uses
SimpleGraph.reachable_iff_reflTransGen,SimpleGraph.fromEdgeSet_adj,Subtype.exttheorem kn_szf_cl_least {n : ℕ} (S T : Set (⊤ : SimpleGraph (Fin n)).edgeSet) (hST : S ⊆ T) (hT : ∀ (a b c : Fin n) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c), (⟨s(a, b), by simpa using hab⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ T → (⟨s(b, c), by simpa using hbc⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ T → (⟨s(a, c), by simpa using hac⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ T) : complete_graph_cycle_closure n S ⊆ T := by rintro ⟨e, he⟩ ⟨a, b, hab, hr⟩ simp only at hab subst hab have key : ∀ c, (SimpleGraph.fromEdgeSet (Subtype.val '' S)).Reachable a c → ∀ h : a ≠ c, (⟨s(a, c), by simpa using h⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ T := by intro c hc rw [SimpleGraph.reachable_iff_reflTransGen] at hc induction hc with | refl => intro h; exact absurd rfl h | @tail c d _ hcd ih => intro had rw [SimpleGraph.fromEdgeSet_adj] at hcd obtain ⟨⟨x, hx, hxv⟩, hcd'⟩ := hcd have hdS : (⟨s(c, d), by simpa using hcd'⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ T := by have : x = ⟨s(c, d), by simpa using hcd'⟩ := Subtype.ext hxv subst this exact hST hx by_cases hac : a = c · subst hac exact hdS · exact hT a c d hac hcd' had (ih hac) hdS exact key b hr (by simpa using he)
The multigraph zero-forcing closure is the least set containing S that is closed under the forcing rule.
If T contains S and is closed under the zero-forcing rule, then structural induction on the definition of `SzfMultiForced` shows that every forced element lies in T: the base elements lie in S ⊆ T, and each induction step preserves membership in T.
theorem kn_szf_least {V : Type*} (μ : V → V → ℕ) (S T : Set V) (hST : S ⊆ T) (hT : ∀ u w, μ u w = 1 → (∀ x, x ≠ w → μ u x ≠ 0 → x ∈ T) → w ∈ T) : szf_multigraph_closure μ S ⊆ T := by intro v hv induction hv with | init v hv => exact hST hv | step u w h1 _ ih => exact hT u w h1 ih
The multigraph zero-forcing closure coincides with the cycle closure for all edge sets if forcing is cycle-sound and simulates triangle transitivity.
We prove set equality by showing both inclusions via minimality (`Set.Subset.antisymm`). For the forward inclusion, `kn_szf_least` applies because S ⊆ cl(S) by `kn_szf_cl_sub` and each forcing step stays within the cycle closure by soundness hypothesis H1 and triangle transitivity (`kn_szf_cl_least`, `kn_szf_cl_tri`). For the reverse inclusion, `kn_szf_cl_least` applies because S ⊆ szf_cl by `SzfMultiForced.init` and completeness hypothesis H2 combined with monotonicity (`kn_szf_least`) guarantees closure under triangle transitivity.
uses
Set.Subset.antisymm,kn_szf_least,kn_szf_cl_sub,kn_szf_cl_least,kn_szf_cl_tri,SzfMultiForced.init,SzfMultiForced.steptheorem kn_szf_eq_of {n : ℕ} (μ : (⊤ : SimpleGraph (Fin n)).edgeSet → (⊤ : SimpleGraph (Fin n)).edgeSet → ℕ) (H1 : ∀ u w, μ u w = 1 → w ∈ complete_graph_cycle_closure n {x | x ≠ w ∧ μ u x ≠ 0}) (H2 : ∀ (a b c : Fin n) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c), (⟨s(a, c), by simpa using hac⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ szf_multigraph_closure μ {⟨s(a, b), by simpa using hab⟩, ⟨s(b, c), by simpa using hbc⟩}) (S : Set (⊤ : SimpleGraph (Fin n)).edgeSet) : szf_multigraph_closure μ S = complete_graph_cycle_closure n S := by apply Set.Subset.antisymm · apply kn_szf_least μ S _ (kn_szf_cl_sub S) intro u w h1 hw exact kn_szf_cl_least _ _ (fun x hx => hw x hx.1 hx.2) (fun a b c hab hbc hac => kn_szf_cl_tri S a b c hab hbc hac) (H1 u w h1) · apply kn_szf_cl_least S _ (fun v hv => SzfMultiForced.init v hv) intro a b c hab hbc hac h1 h2 exact kn_szf_least μ _ (szf_multigraph_closure μ S) (by rintro x (rfl | rfl) · exact h1 · exact h2) (fun u w h hx => SzfMultiForced.step u w h hx) (H2 a b c hab hbc hac)
An edge distinct from w with non-zero multiplicity from u forms an adjacency in the subgraph of non-zero neighbors.
Unfolding adjacency in the graph spanned by {x ≠ w | μ(u, x) ≠ 0} via `SimpleGraph.fromEdgeSet_adj`, the edge {a, b} satisfies both non-identity with w and non-zero multiplicity, so a and b are adjacent.
uses
SimpleGraph.fromEdgeSet_adjtheorem kn_szf_adj {n : ℕ} (μ : (⊤ : SimpleGraph (Fin n)).edgeSet → (⊤ : SimpleGraph (Fin n)).edgeSet → ℕ) (u w : (⊤ : SimpleGraph (Fin n)).edgeSet) (a b : Fin n) (hab : a ≠ b) (hne : (⟨s(a, b), by simpa using hab⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ≠ w) (hμ : μ u ⟨s(a, b), by simpa using hab⟩ ≠ 0) : (SimpleGraph.fromEdgeSet (Subtype.val '' {x | x ≠ w ∧ μ u x ≠ 0})).Adj a b := by rw [SimpleGraph.fromEdgeSet_adj] exact ⟨⟨_, ⟨hne, hμ⟩, rfl⟩, hab⟩
A 4-argument table F with endpoint symmetries lifts to a symmetric edge multiplicity function μ on E(K_n) × E(K_n).
Because F is invariant under swapping vertices within each pair, `Sym2.lift₂` defines a multiplicity function μ on pairs of edges of K_n. Symmetry between edge pairs follows directly from pair symmetry of F, and proving SZF-realizability is reduced to verifying hypotheses H1 and H2 of `kn_szf_eq_of`.
uses
Sym2.lift₂,kn_szf_eq_of,Sym2.indtheorem kn_szf_realizable_of_table {n : ℕ} (F : Fin n → Fin n → Fin n → Fin n → ℕ) (hF : ∀ a₁ a₂ b₁ b₂, F a₁ a₂ b₁ b₂ = F a₂ a₁ b₁ b₂ ∧ F a₁ a₂ b₁ b₂ = F a₁ a₂ b₂ b₁) (hsymm : ∀ i j k l, F i j k l = F k l i j) (H1c : ∀ i j k l : Fin n, i ≠ j → k ≠ l → F i j k l = 1 → (∃ p, p ≠ k ∧ p ≠ l ∧ F i j k p ≠ 0 ∧ F i j p l ≠ 0) ∨ (∃ p q, p ≠ k ∧ p ≠ l ∧ q ≠ k ∧ q ≠ l ∧ p ≠ q ∧ F i j k p ≠ 0 ∧ F i j p q ≠ 0 ∧ F i j q l ≠ 0)) (H2c : ∀ a b c : Fin n, a ≠ b → b ≠ c → a ≠ c → ∃ i j, i ≠ j ∧ F i j a c = 1 ∧ ∀ k l, k ≠ l → F i j k l ≠ 0 → (k = a ∧ l = c ∨ k = c ∧ l = a) ∨ (k = a ∧ l = b ∨ k = b ∧ l = a) ∨ (k = b ∧ l = c ∨ k = c ∧ l = b)) : complete_graphic_matroid_szf_realizable n := by refine ⟨fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1, ?_, kn_szf_eq_of _ ?_ ?_⟩ · rintro ⟨u, hu⟩ ⟨v, hv⟩ induction u using Sym2.ind with | h i j => induction v using Sym2.ind with | h k l => simpa using hsymm i j k l
If F(i, j, k, l) = 1, then edge {k, l} is connected by an intermediate path of length 2 or 3 in the non-zero neighbors of ij, verifying cycle soundness H1.
Hypothesis H1c guarantees that whenever μ(u, w) = 1 with w = {k, l}, there exists a vertex p (or vertices p, q) providing intermediate edges {k, p} and {p, l} with non-zero multiplicity from u that differ from w. Using `kn_szf_adj`, each intermediate edge forms an edge in the subgraph of non-zero neighbors, so concatenating them establishes reachability between k and l, placing {k, l} in the cycle closure.
uses
Sym2.ind,Sym2.lift₂_mk,Sym2.eq_iff.1,congrArg,kn_szf_adj,Ne.symm,Or.inr,Or.inl· rintro ⟨u, hu⟩ ⟨w, hw⟩ h induction u using Sym2.ind with | h i j => induction w using Sym2.ind with | h k l => have hij : i ≠ j := by simpa using hu have hkl : k ≠ l := by simpa using hw simp only [Sym2.lift₂_mk] at h refine ⟨k, l, rfl, ?_⟩ have hne : ∀ (a b : Fin n) (hab : a ≠ b), (a ≠ k ∨ b ≠ l) → (a ≠ l ∨ b ≠ k) → (⟨s(a, b), by simpa using hab⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ≠ ⟨s(k, l), hw⟩ := by intro a b hab h1 h2 heq have := Sym2.eq_iff.1 (congrArg Subtype.val heq) tauto rcases H1c i j k l hij hkl h with ⟨p, hpk, hpl, h1, h2⟩ | ⟨p, q, hpk, hpl, hqk, hql, hpq, h1, h2, h3⟩ · refine (kn_szf_adj (fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1) ⟨s(i, j), hu⟩ _ k p (Ne.symm hpk) (hne k p (Ne.symm hpk) (Or.inr hpl) (Or.inl hkl)) ?_).reachable.trans (kn_szf_adj (fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1) ⟨s(i, j), hu⟩ _ p l hpl (hne p l hpl (Or.inl hpk) (Or.inl hpl)) ?_).reachable · simpa using h1 · simpa using h2 · refine ((kn_szf_adj (fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1) ⟨s(i, j), hu⟩ _ k p (Ne.symm hpk) (hne k p (Ne.symm hpk) (Or.inr hpl) (Or.inl hkl)) ?_).reachable.trans (kn_szf_adj (fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1) ⟨s(i, j), hu⟩ _ p q hpq (hne p q hpq (Or.inl hpk) (Or.inl hpl)) ?_).reachable).trans (kn_szf_adj (fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1) ⟨s(i, j), hu⟩ _ q l hql (hne q l hql (Or.inl hqk) (Or.inl hql)) ?_).reachable · simpa using h1 · simpa using h2 · simpa using h3For every triangle, there exists an edge row that forces the third edge in a single step from the first two, verifying triangle completeness H2.
Hypothesis H2c provides an edge u = {i, j} such that F(i, j, a, c) = 1 and all other non-zero entries in row u are among {a, b} and {b, c}. Applying `SzfMultiForced.step` at u, all other non-zero neighbors belong to the initial set {{a, b}, {b, c}} by `SzfMultiForced.init`, forcing the third edge {a, c}.
uses
SzfMultiForced.step,Sym2.ind,Sym2.lift₂_mk,SzfMultiForced.init,Subtype.ext,Sym2.eq_swap,Or.inl,Or.inr· intro a b c hab hbc hac obtain ⟨i, j, hij, h1, h2⟩ := H2c a b c hab hbc hac refine SzfMultiForced.step ⟨s(i, j), by simpa using hij⟩ _ (by simpa using h1) ?_ rintro ⟨x, hx⟩ hxne hx0 induction x using Sym2.ind with | h k l => have hkl : k ≠ l := by simpa using hx simp only [Sym2.lift₂_mk] at hx0 apply SzfMultiForced.init rcases h2 k l hkl hx0 with (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) | (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) | (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) · exact absurd rfl hxne · exact absurd (Subtype.ext Sym2.eq_swap) hxne · exact Or.inl rfl · exact Or.inl (Subtype.ext Sym2.eq_swap) · exact Or.inr rfl · exact Or.inr (Subtype.ext Sym2.eq_swap)
The table function `kn_szf_table` is invariant under swapping the endpoints of either edge argument.
The bitmask encoding 2^a + 2^b of an edge is symmetric under swapping a and b because addition of natural numbers is commutative (`Nat.add_comm`), so `kn_szf_table` satisfies the required endpoint symmetries.
uses
Nat.add_commtheorem kn_szf_table_symm {n : ℕ} (row : ℕ → List ℕ) (a₁ a₂ b₁ b₂ : Fin n) : kn_szf_table row a₁ a₂ b₁ b₂ = kn_szf_table row a₂ a₁ b₁ b₂ ∧ kn_szf_table row a₁ a₂ b₁ b₂ = kn_szf_table row a₁ a₂ b₂ b₁ := by unfold kn_szf_table kn_szf_code exact ⟨by rw [Nat.add_comm (2 ^ (a₂ : ℕ))], by rw [Nat.add_comm (2 ^ (b₂ : ℕ))]⟩
For every 1 ≤ n ≤ 5, the cycle matroid M(K_n) is SZF-realizable by a multigraph on E(K_n). automation
We perform case analysis on n ∈ {1, 2, 3, 4, 5} using `interval_cases`. For n = 1 and n = 2, the complete graph has at most one edge, so the empty table trivially realizes the matroid. For n = 3, 4, 5, the explicit bitmask tables `kn_szf_row3`, `kn_szf_row4`, and `kn_szf_row5` are supplied to `kn_szf_realizable_of_table`. The required pair symmetry, path connectivity condition (H1c), and triangle forcing condition (H2c) are all verified by kernel evaluation (`decide +kernel`).
uses
kn_szf_realizable_of_table,kn_szf_table_symmtheorem complete_graphic_matroid_szf_realizable_of_le_five (n : ℕ) (h1 : 1 ≤ n) (h5 : n ≤ 5) : complete_graphic_matroid_szf_realizable n := by interval_cases n · exact kn_szf_realizable_of_table (kn_szf_table fun _ => []) (kn_szf_table_symm _) (by decide +kernel) (by decide +kernel) (by decide +kernel) · exact kn_szf_realizable_of_table (kn_szf_table fun _ => []) (kn_szf_table_symm _) (by decide +kernel) (by decide +kernel) (by decide +kernel) · exact kn_szf_realizable_of_table (kn_szf_table kn_szf_row3) (kn_szf_table_symm _) (by decide +kernel) (by decide +kernel) (by decide +kernel) · exact kn_szf_realizable_of_table (kn_szf_table kn_szf_row4) (kn_szf_table_symm _) (by decide +kernel) (by decide +kernel) (by decide +kernel) · exact kn_szf_realizable_of_table (kn_szf_table kn_szf_row5) (kn_szf_table_symm _) (by decide +kernel) (by decide +kernel) (by decide +kernel)
Sym2.ind- To prove a property for all unordered pairs in Sym2 α, it suffices to prove it for canonical pairs s(x, y).
SimpleGraph.Adj.reachable- Adjacent vertices in a simple graph are reachable from one another.
SimpleGraph.fromEdgeSet_adj- In the graph spanned by edge set s, vertices v and w are adjacent if and only if s(v, w) ∈ s and v ≠ w.
Sym2.eq_iff.1- Two unordered pairs are equal if and only if their elements match identically or in swapped order.
SimpleGraph.reachable_iff_reflTransGen- Reachability between two vertices in a simple graph is the reflexive-transitive closure of the adjacency relation.
Subtype.ext- Two subtype elements are equal if and only if their underlying values are equal.
Set.Subset.antisymm- Two sets are equal if each is a subset of the other.
kn_szf_least- The multigraph zero-forcing closure of S under μ is the minimal set containing S and closed under the zero-forcing rule.
kn_szf_cl_sub- Any edge set S of the complete graph is contained in its cycle closure.
kn_szf_cl_least- The cycle closure of S is the minimal set containing S that is closed under triangle transitivity.
kn_szf_cl_tri- If two edges of a triangle belong to the cycle closure of S, then the third edge also belongs to the cycle closure.
SzfMultiForced.init- Every element of the initial set S is zero-forced.
SzfMultiForced.step- If μ(u, w) = 1 and all other non-zero neighbors of u are already forced, then w is forced.
kn_szf_adj- Any edge distinct from w with non-zero multiplicity from u connects its endpoints in the subgraph of non-zero neighbors.
Sym2.lift₂- A 4-argument function invariant under swapping elements in each pair factors through unordered pairs.
kn_szf_eq_of- The multigraph zero-forcing closure equals the cycle closure on all edge sets if forcing is cycle-sound and forces the third edge of any triangle.
Sym2.lift₂_mk- Evaluating a function lifted to unordered pairs on canonical pairs equals the underlying function on the components.
congrArg- Applying a function to equal arguments yields equal results.
Ne.symm- The inequality relation is symmetric.
Or.inr- A disjunction holds if its right disjunct holds.
Or.inl- A disjunction holds if its left disjunct holds.
Sym2.eq_swap- An unordered pair s(a, b) equals s(b, a).
Nat.add_comm- Addition of natural numbers is commutative.
kn_szf_realizable_of_table- A table with endpoint symmetries, pair symmetry, path connectivity (H1c), and triangle forcing (H2c) realizes the cycle matroid.
kn_szf_table_symm- The bitmask table function is invariant under swapping the endpoints of either edge argument.
- The verification of conditions (H1c) and (H2c) for each n ∈ {1, 2, 3, 4, 5} in lines 204–213 is performed entirely by computational reflection in the Lean kernel (`decide +kernel`), which evaluates the finite combinatorial properties directly on the explicit bitmask tables.
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.
theorem kn_szf_cl_sub {n : ℕ} (S : Set (⊤ : SimpleGraph (Fin n)).edgeSet) : S ⊆ complete_graph_cycle_closure n S := by rintro ⟨e, he⟩ hS induction e using Sym2.ind with | h a b => refine ⟨a, b, rfl, SimpleGraph.Adj.reachable ?_⟩ rw [SimpleGraph.fromEdgeSet_adj] exact ⟨⟨_, hS, rfl⟩, by simpa using he⟩theorem kn_szf_cl_tri {n : ℕ} (S : Set (⊤ : SimpleGraph (Fin n)).edgeSet) (a b c : Fin n) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) (h1 : (⟨s(a, b), by simpa using hab⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ complete_graph_cycle_closure n S) (h2 : (⟨s(b, c), by simpa using hbc⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ complete_graph_cycle_closure n S) : (⟨s(a, c), by simpa using hac⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ complete_graph_cycle_closure n S := by obtain ⟨x, y, hxy, r1⟩ := h1 obtain ⟨z, w, hzw, r2⟩ := h2 have r1' : (SimpleGraph.fromEdgeSet (Subtype.val '' S)).Reachable a b := by rcases Sym2.eq_iff.1 hxy with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact r1 · exact r1.symm have r2' : (SimpleGraph.fromEdgeSet (Subtype.val '' S)).Reachable b c := by rcases Sym2.eq_iff.1 hzw with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩ · exact r2 · exact r2.symm exact ⟨a, c, rfl, r1'.trans r2'⟩theorem kn_szf_cl_least {n : ℕ} (S T : Set (⊤ : SimpleGraph (Fin n)).edgeSet) (hST : S ⊆ T) (hT : ∀ (a b c : Fin n) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c), (⟨s(a, b), by simpa using hab⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ T → (⟨s(b, c), by simpa using hbc⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ T → (⟨s(a, c), by simpa using hac⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ T) : complete_graph_cycle_closure n S ⊆ T := by rintro ⟨e, he⟩ ⟨a, b, hab, hr⟩ simp only at hab subst hab have key : ∀ c, (SimpleGraph.fromEdgeSet (Subtype.val '' S)).Reachable a c → ∀ h : a ≠ c, (⟨s(a, c), by simpa using h⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ T := by intro c hc rw [SimpleGraph.reachable_iff_reflTransGen] at hc induction hc with | refl => intro h; exact absurd rfl h | @tail c d _ hcd ih => intro had rw [SimpleGraph.fromEdgeSet_adj] at hcd obtain ⟨⟨x, hx, hxv⟩, hcd'⟩ := hcd have hdS : (⟨s(c, d), by simpa using hcd'⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ T := by have : x = ⟨s(c, d), by simpa using hcd'⟩ := Subtype.ext hxv subst this exact hST hx by_cases hac : a = c · subst hac exact hdS · exact hT a c d hac hcd' had (ih hac) hdS exact key b hr (by simpa using he)theorem kn_szf_least {V : Type*} (μ : V → V → ℕ) (S T : Set V) (hST : S ⊆ T) (hT : ∀ u w, μ u w = 1 → (∀ x, x ≠ w → μ u x ≠ 0 → x ∈ T) → w ∈ T) : szf_multigraph_closure μ S ⊆ T := by intro v hv induction hv with | init v hv => exact hST hv | step u w h1 _ ih => exact hT u w h1 ihtheorem kn_szf_eq_of {n : ℕ} (μ : (⊤ : SimpleGraph (Fin n)).edgeSet → (⊤ : SimpleGraph (Fin n)).edgeSet → ℕ) (H1 : ∀ u w, μ u w = 1 → w ∈ complete_graph_cycle_closure n {x | x ≠ w ∧ μ u x ≠ 0}) (H2 : ∀ (a b c : Fin n) (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c), (⟨s(a, c), by simpa using hac⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ∈ szf_multigraph_closure μ {⟨s(a, b), by simpa using hab⟩, ⟨s(b, c), by simpa using hbc⟩}) (S : Set (⊤ : SimpleGraph (Fin n)).edgeSet) : szf_multigraph_closure μ S = complete_graph_cycle_closure n S := by apply Set.Subset.antisymm · apply kn_szf_least μ S _ (kn_szf_cl_sub S) intro u w h1 hw exact kn_szf_cl_least _ _ (fun x hx => hw x hx.1 hx.2) (fun a b c hab hbc hac => kn_szf_cl_tri S a b c hab hbc hac) (H1 u w h1) · apply kn_szf_cl_least S _ (fun v hv => SzfMultiForced.init v hv) intro a b c hab hbc hac h1 h2 exact kn_szf_least μ _ (szf_multigraph_closure μ S) (by rintro x (rfl | rfl) · exact h1 · exact h2) (fun u w h hx => SzfMultiForced.step u w h hx) (H2 a b c hab hbc hac)theorem kn_szf_adj {n : ℕ} (μ : (⊤ : SimpleGraph (Fin n)).edgeSet → (⊤ : SimpleGraph (Fin n)).edgeSet → ℕ) (u w : (⊤ : SimpleGraph (Fin n)).edgeSet) (a b : Fin n) (hab : a ≠ b) (hne : (⟨s(a, b), by simpa using hab⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ≠ w) (hμ : μ u ⟨s(a, b), by simpa using hab⟩ ≠ 0) : (SimpleGraph.fromEdgeSet (Subtype.val '' {x | x ≠ w ∧ μ u x ≠ 0})).Adj a b := by rw [SimpleGraph.fromEdgeSet_adj] exact ⟨⟨_, ⟨hne, hμ⟩, rfl⟩, hab⟩theorem kn_szf_realizable_of_table {n : ℕ} (F : Fin n → Fin n → Fin n → Fin n → ℕ) (hF : ∀ a₁ a₂ b₁ b₂, F a₁ a₂ b₁ b₂ = F a₂ a₁ b₁ b₂ ∧ F a₁ a₂ b₁ b₂ = F a₁ a₂ b₂ b₁) (hsymm : ∀ i j k l, F i j k l = F k l i j) (H1c : ∀ i j k l : Fin n, i ≠ j → k ≠ l → F i j k l = 1 → (∃ p, p ≠ k ∧ p ≠ l ∧ F i j k p ≠ 0 ∧ F i j p l ≠ 0) ∨ (∃ p q, p ≠ k ∧ p ≠ l ∧ q ≠ k ∧ q ≠ l ∧ p ≠ q ∧ F i j k p ≠ 0 ∧ F i j p q ≠ 0 ∧ F i j q l ≠ 0)) (H2c : ∀ a b c : Fin n, a ≠ b → b ≠ c → a ≠ c → ∃ i j, i ≠ j ∧ F i j a c = 1 ∧ ∀ k l, k ≠ l → F i j k l ≠ 0 → (k = a ∧ l = c ∨ k = c ∧ l = a) ∨ (k = a ∧ l = b ∨ k = b ∧ l = a) ∨ (k = b ∧ l = c ∨ k = c ∧ l = b)) : complete_graphic_matroid_szf_realizable n := by refine ⟨fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1, ?_, kn_szf_eq_of _ ?_ ?_⟩ · rintro ⟨u, hu⟩ ⟨v, hv⟩ induction u using Sym2.ind with | h i j => induction v using Sym2.ind with | h k l => simpa using hsymm i j k l · rintro ⟨u, hu⟩ ⟨w, hw⟩ h induction u using Sym2.ind with | h i j => induction w using Sym2.ind with | h k l => have hij : i ≠ j := by simpa using hu have hkl : k ≠ l := by simpa using hw simp only [Sym2.lift₂_mk] at h refine ⟨k, l, rfl, ?_⟩ have hne : ∀ (a b : Fin n) (hab : a ≠ b), (a ≠ k ∨ b ≠ l) → (a ≠ l ∨ b ≠ k) → (⟨s(a, b), by simpa using hab⟩ : (⊤ : SimpleGraph (Fin n)).edgeSet) ≠ ⟨s(k, l), hw⟩ := by intro a b hab h1 h2 heq have := Sym2.eq_iff.1 (congrArg Subtype.val heq) tauto rcases H1c i j k l hij hkl h with ⟨p, hpk, hpl, h1, h2⟩ | ⟨p, q, hpk, hpl, hqk, hql, hpq, h1, h2, h3⟩ · refine (kn_szf_adj (fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1) ⟨s(i, j), hu⟩ _ k p (Ne.symm hpk) (hne k p (Ne.symm hpk) (Or.inr hpl) (Or.inl hkl)) ?_).reachable.trans (kn_szf_adj (fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1) ⟨s(i, j), hu⟩ _ p l hpl (hne p l hpl (Or.inl hpk) (Or.inl hpl)) ?_).reachable · simpa using h1 · simpa using h2 · refine ((kn_szf_adj (fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1) ⟨s(i, j), hu⟩ _ k p (Ne.symm hpk) (hne k p (Ne.symm hpk) (Or.inr hpl) (Or.inl hkl)) ?_).reachable.trans (kn_szf_adj (fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1) ⟨s(i, j), hu⟩ _ p q hpq (hne p q hpq (Or.inl hpk) (Or.inl hpl)) ?_).reachable).trans (kn_szf_adj (fun u v => Sym2.lift₂ ⟨F, hF⟩ u.1 v.1) ⟨s(i, j), hu⟩ _ q l hql (hne q l hql (Or.inl hqk) (Or.inl hql)) ?_).reachable · simpa using h1 · simpa using h2 · simpa using h3 · intro a b c hab hbc hac obtain ⟨i, j, hij, h1, h2⟩ := H2c a b c hab hbc hac refine SzfMultiForced.step ⟨s(i, j), by simpa using hij⟩ _ (by simpa using h1) ?_ rintro ⟨x, hx⟩ hxne hx0 induction x using Sym2.ind with | h k l => have hkl : k ≠ l := by simpa using hx simp only [Sym2.lift₂_mk] at hx0 apply SzfMultiForced.init rcases h2 k l hkl hx0 with (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) | (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) | (⟨rfl, rfl⟩ | ⟨rfl, rfl⟩) · exact absurd rfl hxne · exact absurd (Subtype.ext Sym2.eq_swap) hxne · exact Or.inl rfl · exact Or.inl (Subtype.ext Sym2.eq_swap) · exact Or.inr rfl · exact Or.inr (Subtype.ext Sym2.eq_swap)/-- Edge code of `s(a, b)`. -/def kn_szf_code {n : ℕ} (a b : Fin n) : ℕ := 2 ^ a.val + 2 ^ b.valdef kn_szf_row5 : ℕ → List ℕ | 3 => [3, 5, 6] | 5 => [3, 9, 10] | 9 => [5, 9, 12] | 17 => [6, 10, 12] | 6 => [3, 17, 18] | 10 => [5, 17, 20] | 18 => [6, 18, 20] | 12 => [9, 17, 24] | 20 => [10, 18, 24] | 24 => [12, 20, 24] | _ => []def kn_szf_row4 : ℕ → List ℕ | 3 => [3, 5, 6] | 5 => [3, 9, 10] | 9 => [5, 9, 6, 10] | 6 => [3, 9, 6, 12] | 10 => [5, 9, 12] | 12 => [6, 10, 12] | _ => []def kn_szf_row3 : ℕ → List ℕ | 3 => [3, 5, 6] | 5 => [3, 5, 6] | 6 => [3, 5, 6] | _ => []def kn_szf_table {n : ℕ} (row : ℕ → List ℕ) (i j k l : Fin n) : ℕ := if kn_szf_code k l ∈ row (kn_szf_code i j) then 1 else 0theorem kn_szf_table_symm {n : ℕ} (row : ℕ → List ℕ) (a₁ a₂ b₁ b₂ : Fin n) : kn_szf_table row a₁ a₂ b₁ b₂ = kn_szf_table row a₂ a₁ b₁ b₂ ∧ kn_szf_table row a₁ a₂ b₁ b₂ = kn_szf_table row a₁ a₂ b₂ b₁ := by unfold kn_szf_table kn_szf_code exact ⟨by rw [Nat.add_comm (2 ^ (a₂ : ℕ))], by rw [Nat.add_comm (2 ^ (b₂ : ℕ))]⟩theorem complete_graphic_matroid_szf_realizable_of_le_five (n : ℕ) (h1 : 1 ≤ n) (h5 : n ≤ 5) : complete_graphic_matroid_szf_realizable n := by interval_cases n · exact kn_szf_realizable_of_table (kn_szf_table fun _ => []) (kn_szf_table_symm _) (by decide +kernel) (by decide +kernel) (by decide +kernel) · exact kn_szf_realizable_of_table (kn_szf_table fun _ => []) (kn_szf_table_symm _) (by decide +kernel) (by decide +kernel) (by decide +kernel) · exact kn_szf_realizable_of_table (kn_szf_table kn_szf_row3) (kn_szf_table_symm _) (by decide +kernel) (by decide +kernel) (by decide +kernel) · exact kn_szf_realizable_of_table (kn_szf_table kn_szf_row4) (kn_szf_table_symm _) (by decide +kernel) (by decide +kernel) (by decide +kernel) · exact kn_szf_realizable_of_table (kn_szf_table kn_szf_row5) (kn_szf_table_symm _) (by decide +kernel) (by decide +kernel) (by decide +kernel)