AFTD Auto-Formalizing Theoretical Domains

complete_graphic_matroid_szf_realizable_iff

theoremverifiedformalization

For 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 parallel edges allowed, has skew zero forcing closure equal to the closure of M(K_n)) if and only if n ≤ 5.

Statement

theorem complete_graphic_matroid_szf_realizable_iff (n : ℕ) (hn : 1 ≤ n) :
    complete_graphic_matroid_szf_realizable n ↔ n ≤ 5
Formalizes
arXiv:2611.15741 Theorem 4.5
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3

Read back from the Lean

For every natural number $n$ satisfying $1 \le n$, the complete graphic matroid on $n$ vertices is SZF-realizable (complete_graphic_matroid_szf_realizable n) if and only if $n \le 5$.

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 equivalence is proved in two parts by reducing to existing classification results for complete graphic matroids. In the forward direction, assuming M(K_n) is SZF-realizable, an indirect argument shows n ≤ 5 because any n ≥ 6 contradicts the known non-realizability result `not_complete_graphic_matroid_szf_realizable_of_six_le`. In the reverse direction, the condition n ≤ 5 together with 1 ≤ n directly implies realizability via `complete_graphic_matroid_szf_realizable_of_le_five`.

  1. If M(K_n) is SZF-realizable, then n ≤ 5.

    We split the equivalence and establish the forward direction by contradiction. Assuming M(K_n) is SZF-realizable, suppose for contradiction that n > 5. Since n is a natural number, this implies 6 ≤ n by linear integer arithmetic (`omega`). But `not_complete_graphic_matroid_szf_realizable_of_six_le` states that M(K_n) is never SZF-realizable when n ≥ 6, contradicting our assumption.

    lines 3–7

    uses not_complete_graphic_matroid_szf_realizable_of_six_le

      constructor
      · intro h
        by_contra hgt
        have h6 : 6 ≤ n := by omega
        exact not_complete_graphic_matroid_szf_realizable_of_six_le n h6 h
  2. If n ≤ 5, then M(K_n) is SZF-realizable.

    For the reverse direction, assume n ≤ 5. Together with the hypothesis 1 ≤ n, the classification lemma `complete_graphic_matroid_szf_realizable_of_le_five` immediately yields that M(K_n) is SZF-realizable.

    lines 8–9

    uses complete_graphic_matroid_szf_realizable_of_le_five

      · intro h
        exact complete_graphic_matroid_szf_realizable_of_le_five n hn h
not_complete_graphic_matroid_szf_realizable_of_six_le
For any natural number n ≥ 6, the cycle matroid M(K_n) of the complete graph is not SZF-realizable.
complete_graphic_matroid_szf_realizable_of_le_five
For any natural number n satisfying 1 ≤ n ≤ 5, the cycle matroid M(K_n) of the complete graph is SZF-realizable.

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 complete_graphic_matroid_szf_realizable_iff (n : ℕ) (hn : 1 ≤ n) :    complete_graphic_matroid_szf_realizable n ↔ n ≤ 5 := by  constructor  · intro h    by_contra hgt    have h6 : 6 ≤ n := by omega    exact not_complete_graphic_matroid_szf_realizable_of_six_le n h6 h  · intro h    exact complete_graphic_matroid_szf_realizable_of_le_five n hn h
See it in the graphDiscuss this resultChallenge it