AFTD Auto-Formalizing Theoretical Domains

complete_graphic_matroid_szf_realizable_of_le_five

theoremverifiedformalization

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

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`).

  1. 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.

    lines 1–9

    uses Sym2.ind, SimpleGraph.Adj.reachable, SimpleGraph.fromEdgeSet_adj

    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⟩
    
  2. 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.

    lines 10–29

    uses Sym2.eq_iff.1

    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'⟩
    
  3. 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.

    lines 30–58

    uses SimpleGraph.reachable_iff_reflTransGen, SimpleGraph.fromEdgeSet_adj, Subtype.ext

    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)
    
  4. 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.

    lines 59–66

    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
    
  5. 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.

    lines 67–88

    uses Set.Subset.antisymm, kn_szf_least, kn_szf_cl_sub, kn_szf_cl_least, kn_szf_cl_tri, SzfMultiForced.init, SzfMultiForced.step

    theorem 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)
    
  6. 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.

    lines 89–97

    uses SimpleGraph.fromEdgeSet_adj

    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⟩
    
  7. 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`.

    lines 98–115

    uses Sym2.lift₂, kn_szf_eq_of, Sym2.ind

    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
  8. 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.

    lines 116–142

    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 h3
  9. For 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}.

    lines 143–160

    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)
    
  10. 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.

    lines 195–200

    uses Nat.add_comm

    theorem 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₂ : ℕ))]⟩
    
  11. 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`).

    lines 201–213

    uses kn_szf_realizable_of_table, kn_szf_table_symm

    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)
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.

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

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)
See it in the graphDiscuss this resultChallenge it