AFTD Auto-Formalizing Theoretical Domains

not_complete_graphic_matroid_szf_realizable_of_six_le

theoremverifiedformalization

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

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.

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

    lines 1–6

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

    lines 7–15

    uses SimpleGraph.fromEdgeSet_adj, Sym2.mem_mk_left

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

    lines 16–27

    uses Sym2.ind, Sym2.mem_mk_left, Sym2.mem_mk_right, Subtype.mk.injEq, Sym2.eq_iff

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

    lines 28–44

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

    lines 45–67

    uses Ne.symm, SimpleGraph.fromEdgeSet_adj, Sym2.eq_swap, cl_inside

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

    lines 68–80

    uses forced_mem, Set.mem_insert_iff, Set.mem_singleton_iff, Subtype.mk.injEq, Sym2.eq_iff

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

    lines 81–93

    uses SzfMultiForced.step, inside3, SzfMultiForced.init, cl_inside

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

    lines 94–106

    uses SzfMultiForced.step, inside3, SzfMultiForced.init, cl_inside

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

    lines 107–112

    uses inside3, one_ne_zero

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

    lines 113–124

    uses Finset.mem_powersetCard, key3

    theorem 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
  11. 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.

    lines 125–141

    uses Finset.exists_mem_ne, Ne.symm, Sym2.mem_iff, Finset.Subset.antisymm

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

    lines 142–153

    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_left

      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)
      omega
    
    end PR1227Six
    
  13. 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.

    lines 154–156

    uses PR1227Six.six_le_aux

    theorem 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

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