complete_graphic_matroid_szf_realizable_iff
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
- 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…
- not_complete_graphic_matroid_szf_realizable_of_six_leFor n ≥ 6 the cycle matroid M(K_n) is not SZF-realizable by any multigraph on E(K_n).
- complete_graphic_matroid_szf_realizable_of_le_fiveFor 1 ≤ n ≤ 5 the cycle matroid M(K_n) is SZF-realizable by some multigraph on E(K_n).
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`.
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.
uses
not_complete_graphic_matroid_szf_realizable_of_six_leconstructor · intro h by_contra hgt have h6 : 6 ≤ n := by omega exact not_complete_graphic_matroid_szf_realizable_of_six_le n h6 h
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.
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
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 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