not_complete_graphic_matroid_szf_realizable_of_six_le
For n ≥ 6 the cycle matroid M(K_n) is not SZF-realizable by any multigraph on E(K_n).
Statement
theorem not_complete_graphic_matroid_szf_realizable_of_six_le (n : ℕ) (hn : 6 ≤ n) :
¬ complete_graphic_matroid_szf_realizable n- Formalizes
- arXiv:2611.15741 Proposition 4.3 (via Corollary 2.12, multigraph version)
- 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…
- 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…
- 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…
- 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 every natural number $n \ge 6$, the complete graphic matroid on $n$ vertices is not "SZF realizable" (¬ complete_graphic_matroid_szf_realizable n). That is, there does not exist any symmetric edge-weight function $\mu$ on pairs of edges of the complete graph $K_n$ (with values in $\mathbb{N}$) whose multigraph zero-forcing closure operator coincides with the graphic matroid (cycle) closure operator on all edge subsets of $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
Suppose for contradiction that a multigraph μ on E(K_n) realizes the cycle matroid of K_n for n ≥ 6. For any 3-element vertex set {a, b, c}, the triangle edge {c, a} lies in the cycle closure of {{a, b}, {b, c}}, which forces the existence of an edge u whose non-zero μ-neighbors are precisely the three edges spanned by {a, b, c}. This associates each 3-element subset of vertices to a unique edge u, yielding an injection from the 3-subsets into E(K_n) and implying (n choose 3) ≤ (n choose 2). However, for n ≥ 6, the identity 3 * (n choose 3) = (n - 2) * (n choose 2) ≥ 4 * (n choose 2) yields (n choose 3) > (n choose 2), a contradiction.
An undirected edge between two distinct vertices in K_n is well-defined.
An edge of K_n is represented as an unordered pair s(a, b) of vertices subject to the condition that a ≠ b. When a ≠ b, this defines an edge in the edge set of the complete graph K_n.
namespace PR1227Six abbrev E (n : ℕ) := (⊤ : SimpleGraph (Fin n)).edgeSet def ed {n : ℕ} (a b : Fin n) (h : a ≠ b) : E n := ⟨s(a, b), by simpa using h⟩
Any vertex reachable from an isolated vertex in an edge-induced subgraph is the vertex itself.
If v is incident to no edges in an edge set F, then any walk starting at v must be empty (a path of length 0). A walk of positive length would begin with an edge in F containing v, contradicting that v ∉ e for all e ∈ F.
uses
SimpleGraph.fromEdgeSet_adj,Sym2.mem_mk_lefttheorem iso_reach {n : ℕ} (F : Set (Sym2 (Fin n))) (v x : Fin n) (hv : ∀ e ∈ F, v ∉ e) (h : (SimpleGraph.fromEdgeSet F).Reachable v x) : v = x := by obtain ⟨w⟩ := h cases w with | nil => rfl | cons hadj _ => rw [SimpleGraph.fromEdgeSet_adj] at hadj exact absurd (Sym2.mem_mk_left _ _) (hv _ hadj.1)
Any edge whose endpoints lie in {a, b, c} must be one of {a, b}, {b, c}, or {c, a}.
Representing an edge x as an unordered pair s(y, z) with distinct endpoints y ≠ z, the condition that both y and z lie in {a, b, c} yields 9 cases. The 3 diagonal cases y = z are ruled out by y ≠ z, and the remaining 6 directed pairs collapse to the 3 undirected edges {a, b}, {b, c}, and {c, a}.
uses
Sym2.ind,Sym2.mem_mk_left,Sym2.mem_mk_right,Subtype.mk.injEq,Sym2.eq_ifftheorem inside3 {n : ℕ} {a b c : Fin n} (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) (x : E n) (hx : ∀ y ∈ x.val, y = a ∨ y = b ∨ y = c) : x = ed a b hab ∨ x = ed b c hbc ∨ x = ed c a (Ne.symm hac) := by obtain ⟨p, hp⟩ := x induction p using Sym2.ind with | _ y z => have hyz : y ≠ z := by simpa using hp have hy := hx y (Sym2.mem_mk_left y z) have hz := hx z (Sym2.mem_mk_right y z) simp only [ed, Subtype.mk.injEq, Sym2.eq_iff] rcases hy with rfl | rfl | rfl <;> rcases hz with rfl | rfl | rfl <;> simp_all
If all edges in S have endpoints in W, then all edges in the cycle closure of S also have endpoints in W.
An edge x = {a, b} in the cycle closure of S corresponds to a path connecting distinct vertices a and b using edges from S. If an endpoint of x (say a) were not in W, it would be incident to no edges in S, so by iso_reach no vertex other than a could be reached from a, contradicting a ≠ b and the existence of the path.
uses
iso_reach,Sym2.mem_iff/-- Closure of a set of edges supported on vertices `W`: its closure stays supported on `W`. -/ theorem cl_inside {n : ℕ} (S : Set (E n)) (W : Fin n → Prop) (hS : ∀ e ∈ S, ∀ y ∈ e.val, W y) (x : E n) (hx : x ∈ complete_graph_cycle_closure n S) : ∀ y ∈ x.val, W y := by obtain ⟨a, b, hab, hr⟩ := hx have hne : a ≠ b := by have := x.2; rw [hab] at this; simpa using this have key : ∀ v, ¬ W v → ∀ u, (SimpleGraph.fromEdgeSet (Subtype.val '' S)).Reachable v u → v = u := fun v hv u h => iso_reach _ v u (by rintro e ⟨e', he', rfl⟩ hve exact hv (hS e' he' v hve)) h intro y hy rw [hab, Sym2.mem_iff] at hy by_contra hW rcases hy with rfl | rfl · exact hne (key _ hW _ hr) · exact hne (key _ hW _ hr.symm).symm
In any triangle on distinct vertices a, b, c, the third edge e_ca lies in the cycle closure of {e_ab, e_bc}, and all edges in this closure have endpoints in {a, b, c}.
The edges e_bc = {c, b} and e_ab = {b, a} form a 2-step walk connecting c to a, so e_ca = {c, a} belongs to the cycle closure of {e_ab, e_bc}. Because both e_ab and e_bc have endpoints in {a, b, c}, the closure preservation lemma cl_inside ensures that every edge in their cycle closure also has both endpoints in {a, b, c}.
uses
Ne.symm,SimpleGraph.fromEdgeSet_adj,Sym2.eq_swap,cl_insidetheorem forced_mem {V : Type*} {μ : V → V → ℕ} {S : Set V} {x : V} (h : x ∈ szf_multigraph_closure μ S) : SzfMultiForced μ S x := h theorem key3 {n : ℕ} (μ : E n → E n → ℕ) (hreal : ∀ S, szf_multigraph_closure μ S = complete_graph_cycle_closure n S) {a b c : Fin n} (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) : ∃ u, ∀ x : E n, μ u x ≠ 0 ↔ ∀ y ∈ x.val, y = a ∨ y = b ∨ y = c := by set eab := ed a b hab set ebc := ed b c hbc set eca := ed c a (Ne.symm hac) have hmem : eca ∈ complete_graph_cycle_closure n {eab, ebc} := by refine ⟨c, a, rfl, ?_⟩ have h1 : (SimpleGraph.fromEdgeSet (Subtype.val '' ({eab, ebc} : Set (E n)))).Adj c b := by rw [SimpleGraph.fromEdgeSet_adj] exact ⟨⟨ebc, by simp, by simp [ebc, ed, Sym2.eq_swap]⟩, Ne.symm hbc⟩ have h2 : (SimpleGraph.fromEdgeSet (Subtype.val '' ({eab, ebc} : Set (E n)))).Adj b a := by rw [SimpleGraph.fromEdgeSet_adj] exact ⟨⟨eab, by simp, by simp [eab, ed, Sym2.eq_swap]⟩, Ne.symm hab⟩ exact h1.reachable.trans h2.reachable have hT : ∀ x ∈ complete_graph_cycle_closure n {eab, ebc}, ∀ y ∈ x.val, y = a ∨ y = b ∨ y = c := cl_inside _ _ (by intro e he y hy rcases he with rfl | rfl <;> simp [eab, ebc, ed] at hy <;> tauto)
Forcing e_ca from {e_ab, e_bc} identifies a vertex u whose non-zero μ-neighbors are supported on {a, b, c}, with μ(u, e_ca) = 1.
Because e_ca ∉ {e_ab, e_bc}, e_ca cannot be an initial edge in the SZF forcing process. It must therefore arise from a forcing step at some vertex u with μ(u, e_ca) = 1, where every other neighbor x ≠ e_ca with μ(u, x) ≠ 0 is forced from {e_ab, e_bc}. By the realization hypothesis, these other neighbors lie in the cycle closure of {e_ab, e_bc}, so all neighbors of u with non-zero weight have endpoints in {a, b, c}.
uses
forced_mem,Set.mem_insert_iff,Set.mem_singleton_iff,Subtype.mk.injEq,Sym2.eq_iffhave hf : SzfMultiForced μ {eab, ebc} eca := forced_mem (by rw [hreal]; exact hmem) have hnS : eca ∉ ({eab, ebc} : Set (E n)) := by simp only [Set.mem_insert_iff, Set.mem_singleton_iff, eca, eab, ebc, ed, Subtype.mk.injEq, Sym2.eq_iff] omega cases hf with | init _ h => exact absurd h hnS | step u _ hu1 hall => have hsupp : ∀ x, μ u x ≠ 0 → ∀ y ∈ x.val, y = a ∨ y = b ∨ y = c := by intro x hx by_cases hxe : x = eca · rw [hxe]; intro y hy; simp [eca, ed] at hy; tauto · exact hT x (by rw [← hreal]; exact hall x hxe hx)
The multiplicity μ(u, e_ab) cannot be zero.
If μ(u, e_ab) = 0, then every neighbor x ≠ e_ca of u with non-zero weight would already be in {e_bc} (as the only possible remaining neighbors are e_bc and e_ab). This would allow u to force e_ca from the singleton {e_bc} alone, placing e_ca = {c, a} in the cycle closure of {e_bc}. But this contradicts support preservation, since the endpoints of e_ca include a, which is outside {b, c}.
uses
SzfMultiForced.step,inside3,SzfMultiForced.init,cl_insidehave hab_nb : μ u eab ≠ 0 := by intro h0 have hfo : SzfMultiForced μ {ebc} eca := SzfMultiForced.step u eca hu1 (fun x hxe hx => by rcases inside3 hab hbc hac x (hsupp x hx) with h | h | h · rw [h] at hx; exact absurd h0 hx · rw [h]; exact SzfMultiForced.init _ rfl · exact absurd h hxe) have hcl : eca ∈ complete_graph_cycle_closure n {ebc} := by rw [← hreal]; exact hfo have := cl_inside {ebc} (fun y => y = b ∨ y = c) (by intro e he y hy; rw [he] at hy; simpa [ebc, ed] using hy) eca hcl a (by simp [eca, ed]) rcases this with h | h · exact hab h · exact hac h
The multiplicity μ(u, e_bc) cannot be zero.
Symmetrically, if μ(u, e_bc) = 0, then e_ca would be forced from the singleton {e_ab} alone, placing e_ca = {c, a} into the cycle closure of {e_ab}. This contradicts support preservation, as c ∉ {a, b}.
uses
SzfMultiForced.step,inside3,SzfMultiForced.init,cl_insidehave hbc_nb : μ u ebc ≠ 0 := by intro h0 have hfo : SzfMultiForced μ {eab} eca := SzfMultiForced.step u eca hu1 (fun x hxe hx => by rcases inside3 hab hbc hac x (hsupp x hx) with h | h | h · rw [h]; exact SzfMultiForced.init _ rfl · rw [h] at hx; exact absurd h0 hx · exact absurd h hxe) have hcl : eca ∈ complete_graph_cycle_closure n {eab} := by rw [← hreal]; exact hfo have := cl_inside {eab} (fun y => y = a ∨ y = b) (by intro e he y hy; rw [he] at hy; simpa [eab, ed] using hy) eca hcl c (by simp [eca, ed]) rcases this with h | h · exact hac h.symm · exact hbc h.symm
The edges x with μ(u, x) ≠ 0 are precisely the edges whose endpoints lie in {a, b, c}.
Every neighbor x with μ(u, x) ≠ 0 has endpoints in {a, b, c}. Conversely, any edge with endpoints in {a, b, c} must be e_ab, e_bc, or e_ca by inside3; the first two have non-zero weight by the previous steps, and μ(u, e_ca) = 1 ≠ 0.
uses
inside3,one_ne_zerorefine ⟨u, fun x => ⟨hsupp x, fun hx => ?_⟩⟩ rcases inside3 hab hbc hac x hx with h | h | h · rw [h]; exact hab_nb · rw [h]; exact hbc_nb · rw [h, hu1]; exact one_ne_zero
There exists a function f mapping every 3-element vertex subset s to an edge u in E(K_n) whose non-zero μ-neighborhood consists of edges supported on s.
For each 3-element subset s in the powerset of vertices of cardinality 3, the three vertices are distinct, so key3 yields an edge u whose non-zero μ-neighbors are precisely the edges on s. The axiom of choice selects such an edge u for each 3-element subset, defining a map f from 3-element vertex subsets to edges.
uses
Finset.mem_powersetCard,key3theorem six_le_aux (n : ℕ) (hn : 6 ≤ n) : ¬ complete_graphic_matroid_szf_realizable n := by rintro ⟨μ, -, hreal⟩ classical have hk : ∀ s ∈ (Finset.univ : Finset (Fin n)).powersetCard 3, ∃ u : E n, ∀ x : E n, μ u x ≠ 0 ↔ ∀ y ∈ x.val, y ∈ s := by intro s hs rw [Finset.mem_powersetCard] at hs obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := Finset.card_eq_three.mp hs.2 obtain ⟨u, hu⟩ := key3 μ hreal hab hbc hac exact ⟨u, fun x => by rw [hu x]; simp⟩ have : Nonempty (E n) := ⟨ed ⟨0, by omega⟩ ⟨1, by omega⟩ (by simp [Fin.ext_iff])⟩ choose! f hf using hk
The map f is injective on 3-element vertex subsets.
If a subset s contains at least two vertices and every edge supported on s is also supported on t, then s ⊆ t, because any vertex a ∈ s can be paired with another vertex b ∈ s to form an edge {a, b} supported on s, forcing a ∈ t. If f(s) = f(t), the edges with non-zero μ-weight from f(s) and f(t) coincide, meaning an edge is supported on s if and only if it is supported on t. By subset antisymmetry, s = t.
uses
Finset.exists_mem_ne,Ne.symm,Sym2.mem_iff,Finset.Subset.antisymmhave sub : ∀ s t : Finset (Fin n), 2 ≤ s.card → (∀ x : E n, (∀ y ∈ x.val, y ∈ s) → (∀ y ∈ x.val, y ∈ t)) → s ⊆ t := by intro s t hs2 h a ha obtain ⟨b, hb, hba⟩ : ∃ b ∈ s, b ≠ a := Finset.exists_mem_ne (by omega) a have := h (ed a b (Ne.symm hba)) (by intro y hy simp only [ed, Sym2.mem_iff] at hy rcases hy with rfl | rfl <;> assumption) exact this a (by simp [ed]) have hinj : Set.InjOn f ((Finset.univ.powersetCard 3 : Finset (Finset (Fin n))) : Set _) := by intro s hs t ht hst have hs3 := (Finset.mem_powersetCard.mp hs).2 have ht3 := (Finset.mem_powersetCard.mp ht).2 have hiff : ∀ x : E n, (∀ y ∈ x.val, y ∈ s) ↔ (∀ y ∈ x.val, y ∈ t) := fun x => by rw [← hf s hs, ← hf t ht, hst] exact Finset.Subset.antisymm (sub s t (by omega) fun x => (hiff x).mp) (sub t s (by omega) fun x => (hiff x).mpr)
The injectivity of f implies (n choose 3) ≤ (n choose 2), which contradicts n ≥ 6.
Injectivity of f maps the (n choose 3) subsets of size 3 into the (n choose 2) edges of K_n, giving (n choose 3) ≤ (n choose 2). But the identity 3 * (n choose 3) = (n - 2) * (n choose 2) together with n ≥ 6 implies 3 * (n choose 3) ≥ 4 * (n choose 2) > 3 * (n choose 2), so (n choose 3) > (n choose 2), an arithmetic contradiction.
uses
Finset.card_le_card_of_injOn,Finset.mem_univ,Finset.card_powersetCard,Nat.choose_succ_right_eq,Nat.choose_pos,Nat.mul_le_mul_lefthave hle := Finset.card_le_card_of_injOn f (t := (Finset.univ : Finset (E n))) (fun s _ => Finset.mem_univ (f s)) hinj rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin, Finset.card_univ, ← SimpleGraph.edgeFinset_card, SimpleGraph.card_edgeFinset_top_eq_card_choose_two, Fintype.card_fin] at hle have h3 : n.choose 3 * 3 = n.choose 2 * (n - 2) := Nat.choose_succ_right_eq n 2 have hpos : 0 < n.choose 2 := Nat.choose_pos (by omega) have hX : n.choose 2 * 4 ≤ n.choose 2 * (n - 2) := Nat.mul_le_mul_left _ (by omega) omega end PR1227Six
For n ≥ 6, the cycle matroid of K_n is not SZF-realizable by any multigraph.
The theorem follows immediately by applying PR1227Six.six_le_aux to n and the assumption 6 ≤ n.
uses
PR1227Six.six_le_auxtheorem not_complete_graphic_matroid_szf_realizable_of_six_le (n : ℕ) (hn : 6 ≤ n) : ¬ complete_graphic_matroid_szf_realizable n := by exact PR1227Six.six_le_aux n hn
SimpleGraph.fromEdgeSet_adj- In the graph generated by an edge set s, vertices v and w are adjacent if and only if {v, w} ∈ s and v ≠ w.
Sym2.mem_mk_left- An element x belongs to the unordered pair {x, y}.
Sym2.ind- To prove a property for all unordered pairs, it suffices to prove it for pairs of the form {x, y}.
Sym2.mem_mk_right- An element y belongs to the unordered pair {x, y}.
Subtype.mk.injEq- Two subtype elements are equal if and only if their underlying values are equal.
Sym2.eq_iff- Two unordered pairs {x, y} and {z, w} are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
iso_reach- If a vertex v is incident to no edges in F, then any vertex reachable from v in the graph spanned by F is v itself.
Sym2.mem_iff- An element a belongs to the unordered pair {b, c} if and only if a = b or a = c.
Ne.symm- If a ≠ b, then b ≠ a.
cl_inside- If every edge in S has both endpoints satisfying W, then every edge in the cycle closure of S also has both endpoints satisfying W.
Sym2.eq_swap- The unordered pair {a, b} equals {b, a}.
forced_mem- An element belongs to the SZF multigraph closure of S if and only if it is forced from S under μ.
Set.mem_insert_iff- An element belongs to insert a s if and only if it equals a or belongs to s.
Set.mem_singleton_iff- An element belongs to the singleton {b} if and only if it equals b.
SzfMultiForced.step- If μ(u, w) = 1 and every other neighbor x ≠ w with μ(u, x) ≠ 0 is forced from S, then w is forced from S.
inside3- Any edge whose vertices all lie in a 3-element set {a, b, c} must be one of the three edges between these vertices.
SzfMultiForced.init- Every element of S is forced from S.
one_ne_zero- The number 1 is not equal to 0.
Finset.mem_powersetCard- A subset s is in the k-element subsets of t if and only if s ⊆ t and |s| = k.
key3- In an SZF-realization of the cycle matroid of K_n, for any three distinct vertices a, b, c, there is a vertex u whose non-zero μ-neighbors are precisely the edges supported on {a, b, c}.
Finset.exists_mem_ne- In a finite set with at least two elements, for any element a there exists an element b ≠ a.
Finset.Subset.antisymm- Two finite sets are equal if each is a subset of the other.
Finset.card_le_card_of_injOn- If an injection maps a finite set s into a finite set t, then |s| ≤ |t|.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
Finset.card_powersetCard- The number of k-element subsets of a finite set s is (|s| choose k).
Nat.choose_succ_right_eq- The binomial identity (n choose (k+1)) * (k+1) = (n choose k) * (n - k).
Nat.choose_pos- If k ≤ n, then (n choose k) > 0.
Nat.mul_le_mul_left- Multiplication by a natural number preserves the ≤ relation.
PR1227Six.six_le_aux- For any n ≥ 6, the cycle matroid of K_n is not SZF-realizable by any multigraph.
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.
namespace PR1227Sixabbrev E (n : ℕ) := (⊤ : SimpleGraph (Fin n)).edgeSetdef ed {n : ℕ} (a b : Fin n) (h : a ≠ b) : E n := ⟨s(a, b), by simpa using h⟩theorem iso_reach {n : ℕ} (F : Set (Sym2 (Fin n))) (v x : Fin n) (hv : ∀ e ∈ F, v ∉ e) (h : (SimpleGraph.fromEdgeSet F).Reachable v x) : v = x := by obtain ⟨w⟩ := h cases w with | nil => rfl | cons hadj _ => rw [SimpleGraph.fromEdgeSet_adj] at hadj exact absurd (Sym2.mem_mk_left _ _) (hv _ hadj.1)theorem inside3 {n : ℕ} {a b c : Fin n} (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) (x : E n) (hx : ∀ y ∈ x.val, y = a ∨ y = b ∨ y = c) : x = ed a b hab ∨ x = ed b c hbc ∨ x = ed c a (Ne.symm hac) := by obtain ⟨p, hp⟩ := x induction p using Sym2.ind with | _ y z => have hyz : y ≠ z := by simpa using hp have hy := hx y (Sym2.mem_mk_left y z) have hz := hx z (Sym2.mem_mk_right y z) simp only [ed, Subtype.mk.injEq, Sym2.eq_iff] rcases hy with rfl | rfl | rfl <;> rcases hz with rfl | rfl | rfl <;> simp_all/-- Closure of a set of edges supported on vertices `W`: its closure stays supported on `W`. -/theorem cl_inside {n : ℕ} (S : Set (E n)) (W : Fin n → Prop) (hS : ∀ e ∈ S, ∀ y ∈ e.val, W y) (x : E n) (hx : x ∈ complete_graph_cycle_closure n S) : ∀ y ∈ x.val, W y := by obtain ⟨a, b, hab, hr⟩ := hx have hne : a ≠ b := by have := x.2; rw [hab] at this; simpa using this have key : ∀ v, ¬ W v → ∀ u, (SimpleGraph.fromEdgeSet (Subtype.val '' S)).Reachable v u → v = u := fun v hv u h => iso_reach _ v u (by rintro e ⟨e', he', rfl⟩ hve exact hv (hS e' he' v hve)) h intro y hy rw [hab, Sym2.mem_iff] at hy by_contra hW rcases hy with rfl | rfl · exact hne (key _ hW _ hr) · exact hne (key _ hW _ hr.symm).symmtheorem forced_mem {V : Type*} {μ : V → V → ℕ} {S : Set V} {x : V} (h : x ∈ szf_multigraph_closure μ S) : SzfMultiForced μ S x := htheorem key3 {n : ℕ} (μ : E n → E n → ℕ) (hreal : ∀ S, szf_multigraph_closure μ S = complete_graph_cycle_closure n S) {a b c : Fin n} (hab : a ≠ b) (hbc : b ≠ c) (hac : a ≠ c) : ∃ u, ∀ x : E n, μ u x ≠ 0 ↔ ∀ y ∈ x.val, y = a ∨ y = b ∨ y = c := by set eab := ed a b hab set ebc := ed b c hbc set eca := ed c a (Ne.symm hac) have hmem : eca ∈ complete_graph_cycle_closure n {eab, ebc} := by refine ⟨c, a, rfl, ?_⟩ have h1 : (SimpleGraph.fromEdgeSet (Subtype.val '' ({eab, ebc} : Set (E n)))).Adj c b := by rw [SimpleGraph.fromEdgeSet_adj] exact ⟨⟨ebc, by simp, by simp [ebc, ed, Sym2.eq_swap]⟩, Ne.symm hbc⟩ have h2 : (SimpleGraph.fromEdgeSet (Subtype.val '' ({eab, ebc} : Set (E n)))).Adj b a := by rw [SimpleGraph.fromEdgeSet_adj] exact ⟨⟨eab, by simp, by simp [eab, ed, Sym2.eq_swap]⟩, Ne.symm hab⟩ exact h1.reachable.trans h2.reachable have hT : ∀ x ∈ complete_graph_cycle_closure n {eab, ebc}, ∀ y ∈ x.val, y = a ∨ y = b ∨ y = c := cl_inside _ _ (by intro e he y hy rcases he with rfl | rfl <;> simp [eab, ebc, ed] at hy <;> tauto) have hf : SzfMultiForced μ {eab, ebc} eca := forced_mem (by rw [hreal]; exact hmem) have hnS : eca ∉ ({eab, ebc} : Set (E n)) := by simp only [Set.mem_insert_iff, Set.mem_singleton_iff, eca, eab, ebc, ed, Subtype.mk.injEq, Sym2.eq_iff] omega cases hf with | init _ h => exact absurd h hnS | step u _ hu1 hall => have hsupp : ∀ x, μ u x ≠ 0 → ∀ y ∈ x.val, y = a ∨ y = b ∨ y = c := by intro x hx by_cases hxe : x = eca · rw [hxe]; intro y hy; simp [eca, ed] at hy; tauto · exact hT x (by rw [← hreal]; exact hall x hxe hx) have hab_nb : μ u eab ≠ 0 := by intro h0 have hfo : SzfMultiForced μ {ebc} eca := SzfMultiForced.step u eca hu1 (fun x hxe hx => by rcases inside3 hab hbc hac x (hsupp x hx) with h | h | h · rw [h] at hx; exact absurd h0 hx · rw [h]; exact SzfMultiForced.init _ rfl · exact absurd h hxe) have hcl : eca ∈ complete_graph_cycle_closure n {ebc} := by rw [← hreal]; exact hfo have := cl_inside {ebc} (fun y => y = b ∨ y = c) (by intro e he y hy; rw [he] at hy; simpa [ebc, ed] using hy) eca hcl a (by simp [eca, ed]) rcases this with h | h · exact hab h · exact hac h have hbc_nb : μ u ebc ≠ 0 := by intro h0 have hfo : SzfMultiForced μ {eab} eca := SzfMultiForced.step u eca hu1 (fun x hxe hx => by rcases inside3 hab hbc hac x (hsupp x hx) with h | h | h · rw [h]; exact SzfMultiForced.init _ rfl · rw [h] at hx; exact absurd h0 hx · exact absurd h hxe) have hcl : eca ∈ complete_graph_cycle_closure n {eab} := by rw [← hreal]; exact hfo have := cl_inside {eab} (fun y => y = a ∨ y = b) (by intro e he y hy; rw [he] at hy; simpa [eab, ed] using hy) eca hcl c (by simp [eca, ed]) rcases this with h | h · exact hac h.symm · exact hbc h.symm refine ⟨u, fun x => ⟨hsupp x, fun hx => ?_⟩⟩ rcases inside3 hab hbc hac x hx with h | h | h · rw [h]; exact hab_nb · rw [h]; exact hbc_nb · rw [h, hu1]; exact one_ne_zerotheorem six_le_aux (n : ℕ) (hn : 6 ≤ n) : ¬ complete_graphic_matroid_szf_realizable n := by rintro ⟨μ, -, hreal⟩ classical have hk : ∀ s ∈ (Finset.univ : Finset (Fin n)).powersetCard 3, ∃ u : E n, ∀ x : E n, μ u x ≠ 0 ↔ ∀ y ∈ x.val, y ∈ s := by intro s hs rw [Finset.mem_powersetCard] at hs obtain ⟨a, b, c, hab, hac, hbc, rfl⟩ := Finset.card_eq_three.mp hs.2 obtain ⟨u, hu⟩ := key3 μ hreal hab hbc hac exact ⟨u, fun x => by rw [hu x]; simp⟩ have : Nonempty (E n) := ⟨ed ⟨0, by omega⟩ ⟨1, by omega⟩ (by simp [Fin.ext_iff])⟩ choose! f hf using hk have sub : ∀ s t : Finset (Fin n), 2 ≤ s.card → (∀ x : E n, (∀ y ∈ x.val, y ∈ s) → (∀ y ∈ x.val, y ∈ t)) → s ⊆ t := by intro s t hs2 h a ha obtain ⟨b, hb, hba⟩ : ∃ b ∈ s, b ≠ a := Finset.exists_mem_ne (by omega) a have := h (ed a b (Ne.symm hba)) (by intro y hy simp only [ed, Sym2.mem_iff] at hy rcases hy with rfl | rfl <;> assumption) exact this a (by simp [ed]) have hinj : Set.InjOn f ((Finset.univ.powersetCard 3 : Finset (Finset (Fin n))) : Set _) := by intro s hs t ht hst have hs3 := (Finset.mem_powersetCard.mp hs).2 have ht3 := (Finset.mem_powersetCard.mp ht).2 have hiff : ∀ x : E n, (∀ y ∈ x.val, y ∈ s) ↔ (∀ y ∈ x.val, y ∈ t) := fun x => by rw [← hf s hs, ← hf t ht, hst] exact Finset.Subset.antisymm (sub s t (by omega) fun x => (hiff x).mp) (sub t s (by omega) fun x => (hiff x).mpr) have hle := Finset.card_le_card_of_injOn f (t := (Finset.univ : Finset (E n))) (fun s _ => Finset.mem_univ (f s)) hinj rw [Finset.card_powersetCard, Finset.card_univ, Fintype.card_fin, Finset.card_univ, ← SimpleGraph.edgeFinset_card, SimpleGraph.card_edgeFinset_top_eq_card_choose_two, Fintype.card_fin] at hle have h3 : n.choose 3 * 3 = n.choose 2 * (n - 2) := Nat.choose_succ_right_eq n 2 have hpos : 0 < n.choose 2 := Nat.choose_pos (by omega) have hX : n.choose 2 * 4 ≤ n.choose 2 * (n - 2) := Nat.mul_le_mul_left _ (by omega) omegaend PR1227Sixtheorem not_complete_graphic_matroid_szf_realizable_of_six_le (n : ℕ) (hn : 6 ≤ n) : ¬ complete_graphic_matroid_szf_realizable n := by exact PR1227Six.six_le_aux n hn