AFTD Auto-Formalizing Theoretical Domains

simple_graph_forced_k4_face_pivot_retains_forcing

theoremverified

If an edge-disjoint triangle packing contains abc and a four-clique abcx has no packed spokes ax, bx, cx, replacing abc by abx preserves the packing size and produces another fully singleton-forced packed triangle.

Statement

theorem simple_graph_forced_k4_face_pivot_retains_forcing (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (a b c x : Fin n) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hfree : ∀ e ∈ ({s(a,x),s(b,x),s(c,x)} : Finset (Sym2 (Fin n))), e ∉ P.biUnion finite_vertex_set_edge_encoding) : let Q := insert ({a,b,x} : Finset (Fin n)) (P.erase {a,b,c}); Q.card = P.card ∧ (∀ t ∈ Q, G.IsNClique 3 t) ∧ (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧ finite_vertex_set_edge_encoding ({a,b,x} : Finset (Fin n)) ⊆ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ Q.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)
Source
Local face-pivot obstruction in the internal-anchor forced-K4 branch of the triangle-packing campaign; no novelty claim.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

We replace the triangle abc in an edge-disjoint triangle packing P with abx to form Q = (P \ {abc}) ∪ {abx}. Because the three spokes ax, bx, cx are disjoint from all packed edges of P and abc is removed, the entire edge set of the 4-clique K₄ = {a, b, c, x} is disjoint from the remaining triangles P \ {abc}. This ensures that abx is a valid triangle, preserves the packing size, and maintains pairwise edge-disjointness. Finally, every edge of abx is singleton-forced in Q by the other faces of the K₄: the edge ab is forced by abc, bx is forced by bcx, and ax is forced by acx, because the other edges of these three triangles are spokes or edges of abc incident to c, none of which belong to Q.

  1. If two vertex sets intersect in at most one vertex, their edge encodings are disjoint.

    Suppose for contradiction that an edge {u, v} belongs to the edge encodings of both sets s and t. Since an edge requires u ≠ v and both endpoints must belong to the respective vertex set, both u and v lie in s ∩ t. Having two distinct elements means |s ∩ t| > 1, contradicting the hypothesis |s ∩ t| ≤ 1.

    lines 8–19

    uses Finset.disjoint_left.mpr, Sym2.ind, Finset.one_lt_card.mpr

      classical
      apply Finset.disjoint_left.mpr
      intro e hes het
      induction e using Sym2.ind with
      | _ u v =>
        simp only [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff,
          Sym2.isDiag_iff_proj_eq] at hes het
        have hm : u ∈ s ∩ t := Finset.mem_inter.mpr ⟨hes.1.1,het.1.1⟩
        have hn : v ∈ s ∩ t := Finset.mem_inter.mpr ⟨hes.1.2,het.1.2⟩
        have hne : u ≠ v := hes.2
        have hh : 1 < (s ∩ t).card := Finset.one_lt_card.mpr ⟨u,hm,v,hn,hne⟩
        omega
  2. The edge encoding of three distinct vertices {a, b, c} consists of the three edges {a, b}, {b, c}, and {c, a}. automation

    By extensionality and case analysis on an unordered pair {u, v} with u ≠ v, the condition that both u, v ∈ {a, b, c} is logically equivalent to {u, v} being one of {a, b}, {b, c}, or {c, a}, which is checked by automated case analysis.

    lines 24–30

    uses Sym2.ind

      classical
      ext e
      induction e using Sym2.ind with
      | _ u v =>
        simp only [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff,
          Sym2.mk_isDiag_iff, Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff]
        aesop
  3. A triangle sharing exactly one edge with an edge set U certifies that this edge is singleton-forced.

    Let T be the edge set of {a, b, c}, which consists of {a, b}, {b, c}, {c, a} by in700_encoding_three. Since {a, b} ∈ U while {b, c} ∉ U and {c, a} ∉ U, the intersection T ∩ U is precisely the singleton {{a, b}}. Since {a, b, c} is a 3-clique in G, T is in the family of triangle edge sets, and having |T ∩ U| = 1 witnesses that {a, b} belongs to the union of singleton-intersecting triangles.

    lines 39–59

    uses in700_encoding_three, Finset.mem_biUnion.mpr, Finset.mem_image.mpr

      classical
      let T := finite_vertex_set_edge_encoding ({a,b,c} : Finset V)
      have henc : T = {s(a,b),s(b,c),s(c,a)} := in700_encoding_three a b c hab hac hbc
      have hcap : T ∩ U = {s(a,b)} := by
        rw [henc]
        ext z
        simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton]
        constructor
        · rintro ⟨rfl | rfl | rfl, hz⟩
          · rfl
          · exact (h2 hz).elim
          · exact (h3 hz).elim
        · rintro rfl
          exact ⟨Or.inl rfl,h1⟩
      apply Finset.mem_biUnion.mpr
      refine ⟨T, Finset.mem_filter.mpr ⟨?_, ?_⟩, ?_⟩
      · unfold simple_graph_triangle_edge_family
        apply Finset.mem_image.mpr
        exact ⟨{a,b,c}, Finset.mem_filter.mpr ⟨Finset.mem_univ _, htri⟩, rfl⟩
      · simp [hcap]
      · simp [henc]
  4. The edges of the four-vertex set {a, b, c, x} are either edges of {a, b, c} or one of the three spokes {a, x}, {b, x}, {c, x}. automation

    Any edge with endpoints in {a, b, c, x} either has both endpoints in {a, b, c}, or has x as one endpoint and a, b, or c as the other. This finite case exhaustion is dispatched by aesop.

    lines 64–71

    uses Sym2.ind

      classical
      intro z hz
      induction z using Sym2.ind with
      | _ u v =>
        simp only [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff,
          Sym2.mk_isDiag_iff, Finset.mem_insert, Finset.mem_singleton, Finset.mem_union,
          Sym2.eq_iff] at hz ⊢
        aesop
  5. All six edges of {a, b, c, x} are disjoint from the edges of the remaining packing P \ {{a, b, c}}.

    Any edge z of {a, b, c, x} is either an edge of {a, b, c} or one of the spokes to x. If z is an edge of {a, b, c}, it cannot belong to any other triangle q ∈ P because triangles in P are pairwise edge-disjoint (in700_encoding_disjoint). If z is a spoke, it cannot belong to any triangle in P by the hypothesis that no spoke is packed. Thus z cannot belong to any triangle in P \ {{a, b, c}}.

    lines 81–91

    uses in700_four_edges_subset, in700_encoding_disjoint, Finset.disjoint_left.mp, Finset.mem_biUnion.mpr

      classical
      apply Finset.disjoint_left.mpr
      intro z hz hU
      obtain ⟨q,hq,hzq⟩ := Finset.mem_biUnion.mp hU
      obtain ⟨hneq,hqP⟩ := Finset.mem_erase.mp hq
      have hor := in700_four_edges_subset a b c x hz
      rcases Finset.mem_union.mp hor with hzold | hzspoke
      · have hd := in700_encoding_disjoint q {a,b,c} (hdisj hqP hp hneq)
        exact Finset.disjoint_left.mp hd hzq hzold
      · apply hfree z hzspoke
        exact Finset.mem_biUnion.mpr ⟨q,hqP,hzq⟩
  6. If a four-element set has cardinality 4, all its elements are pairwise distinct.

    First, any subset of three vertices has cardinality at most 3. If any two of the four vertices a, b, c, x were equal, the set {a, b, c, x} would collapse to at most three vertices, contradicting that its cardinality is 4. Linear arithmetic confirms this for all six pairs.

    lines 96–119

    uses Finset.card_insert_le, Finset.card_singleton

      have le3 (u v w : V) : ({u,v,w} : Finset V).card ≤ 3 := by
        have h1 := Finset.card_insert_le u ({v,w} : Finset V)
        have h2 := Finset.card_insert_le v ({w} : Finset V)
        simp only [Finset.card_singleton] at *
        omega
      refine ⟨?_,?_,?_,?_,?_,?_⟩
      · rintro rfl
        have he : ({a,a,c,x} : Finset V) = {a,c,x} := by ext z; simp <;> tauto
        rw [he] at h; have := le3 a c x; omega
      · rintro rfl
        have he : ({a,b,a,x} : Finset V) = {a,b,x} := by ext z; simp <;> tauto
        rw [he] at h; have := le3 a b x; omega
      · rintro rfl
        have he : ({a,b,c,a} : Finset V) = {a,b,c} := by ext z; simp <;> tauto
        rw [he] at h; have := le3 a b c; omega
      · rintro rfl
        have he : ({a,b,b,x} : Finset V) = {a,b,x} := by ext z; simp <;> tauto
        rw [he] at h; have := le3 a b x; omega
      · rintro rfl
        have he : ({a,b,c,b} : Finset V) = {a,b,c} := by ext z; simp <;> tauto
        rw [he] at h; have := le3 a b c; omega
      · rintro rfl
        have he : ({a,b,c,c} : Finset V) = {a,b,c} := by ext z; simp <;> tauto
        rw [he] at h; have := le3 a b c; omega
  7. If the edge encodings of two vertex sets are disjoint, their intersection contains at most one vertex.

    Suppose for contradiction that the intersection of s and t contains at least two distinct vertices u and v. Then the edge {u, v} belongs to the edge encoding of both s and t, contradicting that their edge encodings are disjoint.

    lines 124–134

    uses Finset.one_lt_card.mp, Finset.disjoint_left.mp

      classical
      by_contra hn
      have hh : 1 < (s ∩ t).card := by omega
      obtain ⟨u,hu,v,hv,huv⟩ := Finset.one_lt_card.mp hh
      obtain ⟨hus,hut⟩ := Finset.mem_inter.mp hu
      obtain ⟨hvs,hvt⟩ := Finset.mem_inter.mp hv
      have h1 : s(u,v) ∈ finite_vertex_set_edge_encoding s := by
        simp [finite_vertex_set_edge_encoding, hus, hvs, huv]
      have h2 : s(u,v) ∈ finite_vertex_set_edge_encoding t := by
        simp [finite_vertex_set_edge_encoding, hut, hvt, huv]
      exact Finset.disjoint_left.mp h h1 h2
  8. The edge encoding operation is monotone with respect to subset inclusion.

    If s ⊆ t, every edge with both endpoints in s also has both endpoints in t, so its edge encoding is a subset of that of t.

    lines 138–143

    uses Finset.mem_sym2_iff

      intro z hz
      obtain ⟨hm,hd⟩ := Finset.mem_filter.mp hz
      apply Finset.mem_filter.mpr
      refine ⟨?_,hd⟩
      rw [Finset.mem_sym2_iff] at hm ⊢
      exact fun a ha => h (hm a ha)
  9. Three pairwise distinct elements form a set of cardinality 3.

    Starting from the singleton {c} of size 1, inserting b ≠ c yields a set of size 2, and inserting a ∉ {b, c} yields a set of size 3.

    lines 148–152

    uses Finset.card_singleton, Finset.card_insert_of_notMem

      have hc : ({c} : Finset V).card = 1 := Finset.card_singleton c
      have hbc' : b ∉ ({c} : Finset V) := by simp [hbc]
      have hb : ({b,c} : Finset V).card = 2 := by rw [Finset.card_insert_of_notMem hbc',hc]
      have ha : a ∉ ({b,c} : Finset V) := by simp [hab,hac]
      rw [Finset.card_insert_of_notMem ha,hb]
  10. Any three-element subset of a 4-clique is a 3-clique.

    The cardinality of the subset is 3, and any two distinct vertices in the subset belong to the 4-clique, so they are adjacent in G.

    lines 157–159

      refine ⟨?_,hcard⟩
      intro u hu v hv hne
      exact hK.1 (hsub hu) (hsub hv) hne
  11. In the pivot theorem, the new triangle T = {a, b, x} is edge-disjoint from R = P \ {{a, b, c}}, and T ∉ R.

    From the 4-clique condition on K = {a, b, c, x}, all four vertices are distinct by in700_four_distinct. Since K is edge-disjoint from R by in700_old_edges_disjoint_four and T ⊆ K, monotonicity (in700_encoding_mono) implies that T is also edge-disjoint from R. Because T contains the edge {a, x}, which cannot belong to R, T cannot be an element of R.

    lines 175–196

    uses in700_four_distinct, in700_old_edges_disjoint_four, in700_encoding_mono

      classical
      obtain ⟨hab,hac,hax,hbc,hbx,hcx⟩ := in700_four_distinct hk4.card_eq
      let K : Finset (Fin n) := {a,b,c,x}
      let T : Finset (Fin n) := {a,b,x}
      let R := P.erase ({a,b,c} : Finset (Fin n))
      let Q := insert T R
      change Q.card = P.card ∧ (∀ t ∈ Q, G.IsNClique 3 t) ∧
        (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧
        finite_vertex_set_edge_encoding T ⊆
          (((simple_graph_triangle_edge_family G).filter
            (fun t => (t ∩ Q.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)
      have hsub : T ⊆ K := by simp [T,K,Finset.subset_iff] <;> tauto
      have hK := in700_old_edges_disjoint_four P a b c x hdisj hp hfree
      change Disjoint (finite_vertex_set_edge_encoding K) (R.biUnion finite_vertex_set_edge_encoding) at hK
      have hT : Disjoint (finite_vertex_set_edge_encoding T) (R.biUnion finite_vertex_set_edge_encoding) :=
        hK.mono_left (in700_encoding_mono hsub)
      have haxT : s(a,x) ∈ finite_vertex_set_edge_encoding T := by
        simp [T,finite_vertex_set_edge_encoding,hax]
      have hTnot : T ∉ R := by
        intro hm
        apply Finset.disjoint_left.mp hT haxT
        exact Finset.mem_biUnion.mpr ⟨T,hm,haxT⟩
  12. The replacement set Q = {T} ∪ R has the same cardinality as P, and T is a 3-clique.

    Since T is a 3-element subset of the 4-clique K, T is a 3-clique by in700_clique_subset and in700_card_three. Removing {a, b, c} from P decreases the size by 1 (Finset.card_erase_of_mem), and adding T ∉ R increases it back by 1 (Finset.card_insert_of_notMem), so |Q| = |P|.

    lines 197–206

    uses in700_clique_subset, in700_card_three, Finset.card_insert_of_notMem, Finset.card_erase_of_mem

      have hTcl : G.IsNClique 3 T := by
        apply in700_clique_subset G K T hk4 hsub
        exact in700_card_three hab hax hbx
      have hcard : Q.card = P.card := by
        change (insert T R).card = P.card
        rw [Finset.card_insert_of_notMem hTnot]
        dsimp [R]
        rw [Finset.card_erase_of_mem hp]
        have : 0 < P.card := Finset.card_pos.mpr ⟨{a,b,c},hp⟩
        omega
  13. The triangles in Q are pairwise edge-disjoint.

    For two distinct triangles in Q, if both are in R ⊆ P, they share at most one vertex by the pairwise disjointness of P (Finset.mem_of_mem_erase). If one is T and the other is u ∈ R, their edge encodings are disjoint, so they intersect in at most one vertex by in700_encoding_disjoint_iff.

    lines 207–220

    uses in700_encoding_disjoint_iff, Finset.mem_of_mem_erase

      have hpair : (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) := by
        intro t ht u hu hne
        simp only [Q,Finset.mem_coe,Finset.mem_insert] at ht hu
        rcases ht with rfl | ht <;> rcases hu with rfl | hu
        · exact (hne rfl).elim
        · apply in700_encoding_disjoint_iff
          apply Finset.disjoint_left.mpr
          intro z hzT hzu
          exact Finset.disjoint_left.mp hT hzT (Finset.mem_biUnion.mpr ⟨u,hu,hzu⟩)
        · apply in700_encoding_disjoint_iff
          apply Finset.disjoint_left.mpr
          intro z hzt hzT
          exact Finset.disjoint_left.mp hT hzT (Finset.mem_biUnion.mpr ⟨t,ht,hzt⟩)
        · exact hdisj (Finset.mem_of_mem_erase ht) (Finset.mem_of_mem_erase hu) hne
  14. No edge incident to c in the 4-clique K belongs to the packed edges of Q, while all three edges of T do.

    For any w ∈ {a, b, x}, the edge {c, w} lies in K and thus not in R (by disjointness of K and R), and does not lie in T = {a, b, x} because c ∉ T. Therefore, none of {c, a}, {c, b}, {c, x} (or their symmetric versions by Sym2.eq_swap) belong to the edges of Q. In contrast, the edges {a, b}, {b, x}, {x, a} of T all belong to the edges of Q because T ∈ Q (Finset.mem_insert_self).

    lines 221–254

    uses Sym2.eq_swap, Finset.mem_insert_self

      have hblock : ∀ w ∈ K, w ≠ c → s(c,w) ∉ Q.biUnion finite_vertex_set_edge_encoding := by
        intro w hw hwc
        have hw' : w = a ∨ w = b ∨ w = x := by simpa [K,hwc] using hw
        have heK : s(c,w) ∈ finite_vertex_set_edge_encoding K := by
          simp [finite_vertex_set_edge_encoding,K,hw',hwc,Ne.symm hwc]
        have heT : s(c,w) ∉ finite_vertex_set_edge_encoding T := by
          simp [finite_vertex_set_edge_encoding,T,Ne.symm hac,Ne.symm hbc,hcx]
        intro hm
        obtain ⟨q,hq,hzq⟩ := Finset.mem_biUnion.mp hm
        simp only [Q,Finset.mem_insert] at hq
        rcases hq with rfl | hq
        · exact heT hzq
        · exact Finset.disjoint_left.mp hK heK (Finset.mem_biUnion.mpr ⟨q,hq,hzq⟩)
      have hca : s(c,a) ∉ Q.biUnion finite_vertex_set_edge_encoding :=
        hblock a (by simp [K]) hac
      have hcb : s(c,b) ∉ Q.biUnion finite_vertex_set_edge_encoding :=
        hblock b (by simp [K]) hbc
      have hcx' : s(c,x) ∉ Q.biUnion finite_vertex_set_edge_encoding :=
        hblock x (by simp [K]) (Ne.symm hcx)
      have hxc : s(x,c) ∉ Q.biUnion finite_vertex_set_edge_encoding := by
        rw [Sym2.eq_swap]; exact hcx'
      have hbc' : s(b,c) ∉ Q.biUnion finite_vertex_set_edge_encoding := by
        rw [Sym2.eq_swap]; exact hcb
      have hac' : s(a,c) ∉ Q.biUnion finite_vertex_set_edge_encoding := by
        rw [Sym2.eq_swap]; exact hca
      have habU : s(a,b) ∈ Q.biUnion finite_vertex_set_edge_encoding := by
        apply Finset.mem_biUnion.mpr
        exact ⟨T,Finset.mem_insert_self T R,by simp [T,finite_vertex_set_edge_encoding,hab]⟩
      have hbxU : s(b,x) ∈ Q.biUnion finite_vertex_set_edge_encoding := by
        apply Finset.mem_biUnion.mpr
        exact ⟨T,Finset.mem_insert_self T R,by simp [T,finite_vertex_set_edge_encoding,hbx]⟩
      have hxaU : s(x,a) ∈ Q.biUnion finite_vertex_set_edge_encoding := by
        apply Finset.mem_biUnion.mpr
        exact ⟨T,Finset.mem_insert_self T R,by simp [T,finite_vertex_set_edge_encoding,Ne.symm hax]⟩
  15. All triangles in Q are 3-cliques, and every edge of T is singleton-forced in Q.

    Every triangle in Q is either T (already shown to be a 3-clique) or in R ⊆ P (which are 3-cliques by hypothesis). For singleton forcing of the edges of T, we exhibit three witness triangles in G using in700_triangle_witness: edge {a, b} is forced by {a, b, c} because {b, c} and {c, a} are not in Q; edge {b, x} is forced by {b, x, c} because {x, c} and {c, b} are not in Q; and edge {x, a} is forced by {x, a, c} because {a, c} and {c, x} are not in Q.

    lines 255–275

    uses in700_clique_subset, in700_card_three, in700_encoding_three, in700_triangle_witness

      have hxca : G.IsNClique 3 ({x,a,c} : Finset (Fin n)) := by
        apply in700_clique_subset G K _ hk4
        · simp [K,Finset.subset_iff] <;> tauto
        · exact in700_card_three (Ne.symm hax) (Ne.symm hcx) hac
      have hbxc : G.IsNClique 3 ({b,x,c} : Finset (Fin n)) := by
        apply in700_clique_subset G K _ hk4
        · simp [K,Finset.subset_iff] <;> tauto
        · exact in700_card_three hbx hbc (Ne.symm hcx)
      refine ⟨hcard, ?_, hpair, ?_⟩
      · intro t ht
        simp only [Q,Finset.mem_insert] at ht
        rcases ht with rfl | ht
        · exact hTcl
        · exact htri t (Finset.mem_of_mem_erase ht)
      · intro z hz
        rw [in700_encoding_three a b x hab hax hbx] at hz
        simp only [Finset.mem_insert,Finset.mem_singleton] at hz
        rcases hz with rfl | rfl | rfl
        · exact in700_triangle_witness G _ a b c hab hac hbc (htri _ hp) habU hbc' hca
        · exact in700_triangle_witness G _ b x c hbx hbc (Ne.symm hcx) hbxc hbxU hxc hcb
        · exact in700_triangle_witness G _ x a c (Ne.symm hax) (Ne.symm hcx) hac hxca hxaU hac' hcx'
  16. The main theorem follows immediately from In700.in700_main.

    The theorem simple_graph_forced_k4_face_pivot_retains_forcing directly delegates to In700.in700_main with the identical hypotheses.

    line 279

    uses In700.in700_main

      exact In700.in700_main n G P a b c x htri hdisj hp hk4 hfree
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element of the first belongs to the second.
Sym2.ind
To prove a property for all unordered pairs, it suffices to prove it for pairs of the form s(x, y).
Finset.one_lt_card.mpr
A finite set has cardinality strictly greater than 1 if it contains at least two distinct elements.
in700_encoding_three
The edge encoding of a set of three pairwise distinct vertices {a, b, c} is {s(a, b), s(b, c), s(c, a)}.
Finset.mem_biUnion.mpr
An element belongs to a bounded union if it belongs to the image set of some element in the index set.
Finset.mem_image.mpr
An element y is in the image of a set s under f if there is an x in s with f(x) = y.
in700_four_edges_subset
The edges spanned by {a, b, c, x} are contained in the edges spanned by {a, b, c} together with the three spokes {s(a, x), s(b, x), s(c, x)}.
in700_encoding_disjoint
If two vertex sets have an intersection of size at most 1, their edge encodings are disjoint.
Finset.disjoint_left.mp
If two sets are disjoint, an element of the first set cannot belong to the second set.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1.
Finset.card_singleton
A singleton set has cardinality 1.
Finset.one_lt_card.mp
If a finite set has cardinality strictly greater than 1, it contains at least two distinct elements.
Finset.mem_sym2_iff
An unordered pair belongs to the symmetric square of s if and only if both of its endpoints belong to s.
Finset.card_insert_of_notMem
Inserting an element not present in a finite set increases its cardinality by exactly 1.
in700_four_distinct
If a set of four elements {a, b, c, x} has cardinality 4, all six pairs among them are distinct.
in700_old_edges_disjoint_four
If P is a pairwise edge-disjoint packing containing {a, b, c} and none of the spokes ax, bx, cx appear in P, then the 6 edges on {a, b, c, x} are disjoint from all edges of P \ {{a, b, c}}.
in700_encoding_mono
The edge encoding operation preserves inclusion: if s ⊆ t then the edges of s are a subset of the edges of t.
in700_clique_subset
Any three-element subset of a 4-clique is a 3-clique.
in700_card_three
If three elements are pairwise distinct, the set containing them has cardinality 3.
Finset.card_erase_of_mem
Removing an element from a finite set decreases its cardinality by 1.
in700_encoding_disjoint_iff
If the edge encodings of two vertex sets are disjoint, the sets share at most one vertex.
Finset.mem_of_mem_erase
An element of s \ {a} is also an element of s.
Sym2.eq_swap
The unordered pair s(a, b) equals s(b, a).
Finset.mem_insert_self
An element always belongs to the set obtained by inserting it.
in700_triangle_witness
If a triangle has one edge in U and its other two edges outside U, that edge is singleton-forced by this triangle.
In700.in700_main
Pivoting a triangle face {a, b, c} in a packing P to {a, b, x} within a 4-clique {a, b, c, x} with no packed spokes preserves packing cardinality, clique properties, pairwise edge-disjointness, and singleton forcing of all edges of the new triangle.

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

set_option maxHeartbeats 1000000set_option maxRecDepth 10000open scoped Sym2namespace In700lemma in700_encoding_disjoint {V : Type*} [DecidableEq V] (s t : Finset V)    (h : (s ∩ t).card ≤ 1) :    Disjoint (finite_vertex_set_edge_encoding s) (finite_vertex_set_edge_encoding t) := by  classical  apply Finset.disjoint_left.mpr  intro e hes het  induction e using Sym2.ind with  | _ u v =>    simp only [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff,      Sym2.isDiag_iff_proj_eq] at hes het    have hm : u ∈ s ∩ t := Finset.mem_inter.mpr ⟨hes.1.1,het.1.1⟩    have hn : v ∈ s ∩ t := Finset.mem_inter.mpr ⟨hes.1.2,het.1.2⟩    have hne : u ≠ v := hes.2    have hh : 1 < (s ∩ t).card := Finset.one_lt_card.mpr ⟨u,hm,v,hn,hne⟩    omegalemma in700_encoding_three {V : Type*} [DecidableEq V] (a b c : V)    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :    finite_vertex_set_edge_encoding ({a,b,c} : Finset V) = {s(a,b),s(b,c),s(c,a)} := by  classical  ext e  induction e using Sym2.ind with  | _ u v =>    simp only [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff,      Sym2.mk_isDiag_iff, Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff]    aesoplemma in700_triangle_witness {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) (U : Finset (Sym2 V)) (a b c : V)    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c)    (htri : G.IsNClique 3 ({a,b,c} : Finset V))    (h1 : s(a,b) ∈ U) (h2 : s(b,c) ∉ U) (h3 : s(c,a) ∉ U) :    s(a,b) ∈ (((simple_graph_triangle_edge_family G).filter      (fun t => (t ∩ U).card = 1)).biUnion id) := by  classical  let T := finite_vertex_set_edge_encoding ({a,b,c} : Finset V)  have henc : T = {s(a,b),s(b,c),s(c,a)} := in700_encoding_three a b c hab hac hbc  have hcap : T ∩ U = {s(a,b)} := by    rw [henc]    ext z    simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton]    constructor    · rintro ⟨rfl | rfl | rfl, hz⟩      · rfl      · exact (h2 hz).elim      · exact (h3 hz).elim    · rintro rfl      exact ⟨Or.inl rfl,h1⟩  apply Finset.mem_biUnion.mpr  refine ⟨T, Finset.mem_filter.mpr ⟨?_, ?_⟩, ?_⟩  · unfold simple_graph_triangle_edge_family    apply Finset.mem_image.mpr    exact ⟨{a,b,c}, Finset.mem_filter.mpr ⟨Finset.mem_univ _, htri⟩, rfl⟩  · simp [hcap]  · simp [henc]lemma in700_four_edges_subset {V : Type*} [DecidableEq V] (a b c x : V) :    finite_vertex_set_edge_encoding ({a,b,c,x} : Finset V) ⊆      finite_vertex_set_edge_encoding ({a,b,c} : Finset V) ∪ {s(a,x),s(b,x),s(c,x)} := by  classical  intro z hz  induction z using Sym2.ind with  | _ u v =>    simp only [finite_vertex_set_edge_encoding, Finset.mem_filter, Finset.mk_mem_sym2_iff,      Sym2.mk_isDiag_iff, Finset.mem_insert, Finset.mem_singleton, Finset.mem_union,      Sym2.eq_iff] at hz ⊢    aesoplemma in700_old_edges_disjoint_four {V : Type*} [Fintype V] [DecidableEq V]    (P : Finset (Finset V)) (a b c x : V)    (hdisj : (P : Set (Finset V)).Pairwise (fun t u => (t ∩ u).card ≤ 1))    (hp : ({a,b,c} : Finset V) ∈ P)    (hfree : ∀ e ∈ ({s(a,x),s(b,x),s(c,x)} : Finset (Sym2 V)),      e ∉ P.biUnion finite_vertex_set_edge_encoding) :    Disjoint (finite_vertex_set_edge_encoding ({a,b,c,x} : Finset V))      ((P.erase {a,b,c}).biUnion finite_vertex_set_edge_encoding) := by  classical  apply Finset.disjoint_left.mpr  intro z hz hU  obtain ⟨q,hq,hzq⟩ := Finset.mem_biUnion.mp hU  obtain ⟨hneq,hqP⟩ := Finset.mem_erase.mp hq  have hor := in700_four_edges_subset a b c x hz  rcases Finset.mem_union.mp hor with hzold | hzspoke  · have hd := in700_encoding_disjoint q {a,b,c} (hdisj hqP hp hneq)    exact Finset.disjoint_left.mp hd hzq hzold  · apply hfree z hzspoke    exact Finset.mem_biUnion.mpr ⟨q,hqP,hzq⟩lemma in700_four_distinct {V : Type*} [DecidableEq V] {a b c x : V}    (h : ({a,b,c,x} : Finset V).card = 4) :    a ≠ b ∧ a ≠ c ∧ a ≠ x ∧ b ≠ c ∧ b ≠ x ∧ c ≠ x := by  have le3 (u v w : V) : ({u,v,w} : Finset V).card ≤ 3 := by    have h1 := Finset.card_insert_le u ({v,w} : Finset V)    have h2 := Finset.card_insert_le v ({w} : Finset V)    simp only [Finset.card_singleton] at *    omega  refine ⟨?_,?_,?_,?_,?_,?_⟩  · rintro rfl    have he : ({a,a,c,x} : Finset V) = {a,c,x} := by ext z; simp <;> tauto    rw [he] at h; have := le3 a c x; omega  · rintro rfl    have he : ({a,b,a,x} : Finset V) = {a,b,x} := by ext z; simp <;> tauto    rw [he] at h; have := le3 a b x; omega  · rintro rfl    have he : ({a,b,c,a} : Finset V) = {a,b,c} := by ext z; simp <;> tauto    rw [he] at h; have := le3 a b c; omega  · rintro rfl    have he : ({a,b,b,x} : Finset V) = {a,b,x} := by ext z; simp <;> tauto    rw [he] at h; have := le3 a b x; omega  · rintro rfl    have he : ({a,b,c,b} : Finset V) = {a,b,c} := by ext z; simp <;> tauto    rw [he] at h; have := le3 a b c; omega  · rintro rfl    have he : ({a,b,c,c} : Finset V) = {a,b,c} := by ext z; simp <;> tauto    rw [he] at h; have := le3 a b c; omegalemma in700_encoding_disjoint_iff {V : Type*} [DecidableEq V] (s t : Finset V)    (h : Disjoint (finite_vertex_set_edge_encoding s) (finite_vertex_set_edge_encoding t)) :    (s ∩ t).card ≤ 1 := by  classical  by_contra hn  have hh : 1 < (s ∩ t).card := by omega  obtain ⟨u,hu,v,hv,huv⟩ := Finset.one_lt_card.mp hh  obtain ⟨hus,hut⟩ := Finset.mem_inter.mp hu  obtain ⟨hvs,hvt⟩ := Finset.mem_inter.mp hv  have h1 : s(u,v) ∈ finite_vertex_set_edge_encoding s := by    simp [finite_vertex_set_edge_encoding, hus, hvs, huv]  have h2 : s(u,v) ∈ finite_vertex_set_edge_encoding t := by    simp [finite_vertex_set_edge_encoding, hut, hvt, huv]  exact Finset.disjoint_left.mp h h1 h2lemma in700_encoding_mono {V : Type*} [DecidableEq V] {s t : Finset V}    (h : s ⊆ t) : finite_vertex_set_edge_encoding s ⊆ finite_vertex_set_edge_encoding t := by  intro z hz  obtain ⟨hm,hd⟩ := Finset.mem_filter.mp hz  apply Finset.mem_filter.mpr  refine ⟨?_,hd⟩  rw [Finset.mem_sym2_iff] at hm ⊢  exact fun a ha => h (hm a ha)lemma in700_card_three {V : Type*} [DecidableEq V] {a b c : V}    (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) :    ({a,b,c} : Finset V).card = 3 := by  have hc : ({c} : Finset V).card = 1 := Finset.card_singleton c  have hbc' : b ∉ ({c} : Finset V) := by simp [hbc]  have hb : ({b,c} : Finset V).card = 2 := by rw [Finset.card_insert_of_notMem hbc',hc]  have ha : a ∉ ({b,c} : Finset V) := by simp [hab,hac]  rw [Finset.card_insert_of_notMem ha,hb]lemma in700_clique_subset {V : Type*} [DecidableEq V] (G : SimpleGraph V)    (K t : Finset V) (hK : G.IsNClique 4 K) (hsub : t ⊆ K) (hcard : t.card = 3) :    G.IsNClique 3 t := by  refine ⟨?_,hcard⟩  intro u hu v hv hne  exact hK.1 (hsub hu) (hsub hv) hnetheorem in700_main (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj]    (P : Finset (Finset (Fin n))) (a b c x : Fin n)    (htri : ∀ t ∈ P, G.IsNClique 3 t)    (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1))    (hp : ({a,b,c} : Finset (Fin n)) ∈ P)    (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n)))    (hfree : ∀ e ∈ ({s(a,x),s(b,x),s(c,x)} : Finset (Sym2 (Fin n))),      e ∉ P.biUnion finite_vertex_set_edge_encoding) :    let Q := insert ({a,b,x} : Finset (Fin n)) (P.erase {a,b,c});    Q.card = P.card ∧ (∀ t ∈ Q, G.IsNClique 3 t) ∧    (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧    finite_vertex_set_edge_encoding ({a,b,x} : Finset (Fin n)) ⊆      (((simple_graph_triangle_edge_family G).filter        (fun t => (t ∩ Q.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) := by  classical  obtain ⟨hab,hac,hax,hbc,hbx,hcx⟩ := in700_four_distinct hk4.card_eq  let K : Finset (Fin n) := {a,b,c,x}  let T : Finset (Fin n) := {a,b,x}  let R := P.erase ({a,b,c} : Finset (Fin n))  let Q := insert T R  change Q.card = P.card ∧ (∀ t ∈ Q, G.IsNClique 3 t) ∧    (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧    finite_vertex_set_edge_encoding T ⊆      (((simple_graph_triangle_edge_family G).filter        (fun t => (t ∩ Q.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)  have hsub : T ⊆ K := by simp [T,K,Finset.subset_iff] <;> tauto  have hK := in700_old_edges_disjoint_four P a b c x hdisj hp hfree  change Disjoint (finite_vertex_set_edge_encoding K) (R.biUnion finite_vertex_set_edge_encoding) at hK  have hT : Disjoint (finite_vertex_set_edge_encoding T) (R.biUnion finite_vertex_set_edge_encoding) :=    hK.mono_left (in700_encoding_mono hsub)  have haxT : s(a,x) ∈ finite_vertex_set_edge_encoding T := by    simp [T,finite_vertex_set_edge_encoding,hax]  have hTnot : T ∉ R := by    intro hm    apply Finset.disjoint_left.mp hT haxT    exact Finset.mem_biUnion.mpr ⟨T,hm,haxT⟩  have hTcl : G.IsNClique 3 T := by    apply in700_clique_subset G K T hk4 hsub    exact in700_card_three hab hax hbx  have hcard : Q.card = P.card := by    change (insert T R).card = P.card    rw [Finset.card_insert_of_notMem hTnot]    dsimp [R]    rw [Finset.card_erase_of_mem hp]    have : 0 < P.card := Finset.card_pos.mpr ⟨{a,b,c},hp⟩    omega  have hpair : (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) := by    intro t ht u hu hne    simp only [Q,Finset.mem_coe,Finset.mem_insert] at ht hu    rcases ht with rfl | ht <;> rcases hu with rfl | hu    · exact (hne rfl).elim    · apply in700_encoding_disjoint_iff      apply Finset.disjoint_left.mpr      intro z hzT hzu      exact Finset.disjoint_left.mp hT hzT (Finset.mem_biUnion.mpr ⟨u,hu,hzu⟩)    · apply in700_encoding_disjoint_iff      apply Finset.disjoint_left.mpr      intro z hzt hzT      exact Finset.disjoint_left.mp hT hzT (Finset.mem_biUnion.mpr ⟨t,ht,hzt⟩)    · exact hdisj (Finset.mem_of_mem_erase ht) (Finset.mem_of_mem_erase hu) hne  have hblock : ∀ w ∈ K, w ≠ c → s(c,w) ∉ Q.biUnion finite_vertex_set_edge_encoding := by    intro w hw hwc    have hw' : w = a ∨ w = b ∨ w = x := by simpa [K,hwc] using hw    have heK : s(c,w) ∈ finite_vertex_set_edge_encoding K := by      simp [finite_vertex_set_edge_encoding,K,hw',hwc,Ne.symm hwc]    have heT : s(c,w) ∉ finite_vertex_set_edge_encoding T := by      simp [finite_vertex_set_edge_encoding,T,Ne.symm hac,Ne.symm hbc,hcx]    intro hm    obtain ⟨q,hq,hzq⟩ := Finset.mem_biUnion.mp hm    simp only [Q,Finset.mem_insert] at hq    rcases hq with rfl | hq    · exact heT hzq    · exact Finset.disjoint_left.mp hK heK (Finset.mem_biUnion.mpr ⟨q,hq,hzq⟩)  have hca : s(c,a) ∉ Q.biUnion finite_vertex_set_edge_encoding :=    hblock a (by simp [K]) hac  have hcb : s(c,b) ∉ Q.biUnion finite_vertex_set_edge_encoding :=    hblock b (by simp [K]) hbc  have hcx' : s(c,x) ∉ Q.biUnion finite_vertex_set_edge_encoding :=    hblock x (by simp [K]) (Ne.symm hcx)  have hxc : s(x,c) ∉ Q.biUnion finite_vertex_set_edge_encoding := by    rw [Sym2.eq_swap]; exact hcx'  have hbc' : s(b,c) ∉ Q.biUnion finite_vertex_set_edge_encoding := by    rw [Sym2.eq_swap]; exact hcb  have hac' : s(a,c) ∉ Q.biUnion finite_vertex_set_edge_encoding := by    rw [Sym2.eq_swap]; exact hca  have habU : s(a,b) ∈ Q.biUnion finite_vertex_set_edge_encoding := by    apply Finset.mem_biUnion.mpr    exact ⟨T,Finset.mem_insert_self T R,by simp [T,finite_vertex_set_edge_encoding,hab]⟩  have hbxU : s(b,x) ∈ Q.biUnion finite_vertex_set_edge_encoding := by    apply Finset.mem_biUnion.mpr    exact ⟨T,Finset.mem_insert_self T R,by simp [T,finite_vertex_set_edge_encoding,hbx]⟩  have hxaU : s(x,a) ∈ Q.biUnion finite_vertex_set_edge_encoding := by    apply Finset.mem_biUnion.mpr    exact ⟨T,Finset.mem_insert_self T R,by simp [T,finite_vertex_set_edge_encoding,Ne.symm hax]⟩  have hxca : G.IsNClique 3 ({x,a,c} : Finset (Fin n)) := by    apply in700_clique_subset G K _ hk4    · simp [K,Finset.subset_iff] <;> tauto    · exact in700_card_three (Ne.symm hax) (Ne.symm hcx) hac  have hbxc : G.IsNClique 3 ({b,x,c} : Finset (Fin n)) := by    apply in700_clique_subset G K _ hk4    · simp [K,Finset.subset_iff] <;> tauto    · exact in700_card_three hbx hbc (Ne.symm hcx)  refine ⟨hcard, ?_, hpair, ?_⟩  · intro t ht    simp only [Q,Finset.mem_insert] at ht    rcases ht with rfl | ht    · exact hTcl    · exact htri t (Finset.mem_of_mem_erase ht)  · intro z hz    rw [in700_encoding_three a b x hab hax hbx] at hz    simp only [Finset.mem_insert,Finset.mem_singleton] at hz    rcases hz with rfl | rfl | rfl    · exact in700_triangle_witness G _ a b c hab hac hbc (htri _ hp) habU hbc' hca    · exact in700_triangle_witness G _ b x c hbx hbc (Ne.symm hcx) hbxc hbxU hxc hcb    · exact in700_triangle_witness G _ x a c (Ne.symm hax) (Ne.symm hcx) hac hxca hxaU hac' hcx'end In700theorem simple_graph_forced_k4_face_pivot_retains_forcing (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (a b c x : Fin n) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hfree : ∀ e ∈ ({s(a,x),s(b,x),s(c,x)} : Finset (Sym2 (Fin n))), e ∉ P.biUnion finite_vertex_set_edge_encoding) : let Q := insert ({a,b,x} : Finset (Fin n)) (P.erase {a,b,c}); Q.card = P.card ∧ (∀ t ∈ Q, G.IsNClique 3 t) ∧ (Q : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1) ∧ finite_vertex_set_edge_encoding ({a,b,x} : Finset (Fin n)) ⊆ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ Q.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) := by  exact In700.in700_main n G P a b c x htri hdisj hp hk4 hfree
See it in the graphDiscuss this resultChallenge it