AFTD Auto-Formalizing Theoretical Domains

finite_packing_k4_old_edges_avoid

theoremverified

For an edge-disjoint family containing abc whose union avoids the three spokes from x, removing abc leaves a family whose encoded edges avoid every edge among a,b,c,x.

Statement

theorem finite_packing_k4_old_edges_avoid {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)
Source
Core packing reduction in simple_graph_forced_k4_face_pivot_retains_forcing.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

To show that the complete graph on {a, b, c, x} is edge-disjoint from the union of the remaining blocks in P \ {{a, b, c}}, we argue by contradiction. Any edge among {a, b, c, x} is either an edge within the triangle {a, b, c} or one of the three spokes connecting x to a, b, or c. If it were an edge within {a, b, c}, it cannot belong to any other block q ∈ P because blocks intersect in at most one vertex, ensuring disjoint edge sets. If it were a spoke to x, it cannot belong to any block q ∈ P because the spokes are assumed to be completely avoided by the family P.

  1. An edge common to the encodings of s and t must connect two distinct vertices that both lie in s and in t.

    To show that the edge encodings of s and t are disjoint, we suppose for contradiction that they share an edge e. By quotient induction, e is an unordered pair s(u, v). Unfolding the edge encoding definition shows that u ≠ v and both endpoints belong to s as well as to t.

    lines 6–12

    uses Finset.disjoint_left.mpr, Sym2.ind, Finset.mem_filter, Finset.mk_mem_sym2_iff, Sym2.isDiag_iff_proj_eq

      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
  2. A shared edge implies |s ∩ t| > 1, contradicting |s ∩ t| ≤ 1.

    Since both endpoints u and v belong to s ∩ t and u ≠ v, the intersection contains at least two distinct elements, so |s ∩ t| > 1. This contradicts the hypothesis |s ∩ t| ≤ 1. Linear arithmetic over ℕ (omega) closes the contradiction.

    lines 13–17

    uses Finset.mem_inter.mpr, Finset.one_lt_card.mpr

        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
  3. Every edge on {a, b, c, x} is either an edge on {a, b, c} or one of the three spokes to x. automation

    Let z be an edge on {a, b, c, x}. Writing z as an unordered pair s(u, v) with u ≠ v, we unfold the definitions of edge encoding and set membership. The automated tactic aesop verifies all cases: if neither endpoint is x, both belong to {a, b, c}; if one endpoint is x, the other must be a, b, or c, matching one of the three spokes.

    lines 21–28

    uses Sym2.ind, Finset.mem_filter, Finset.mk_mem_sym2_iff, Sym2.mk_isDiag_iff, Finset.mem_insert, Finset.mem_singleton, Finset.mem_union, Sym2.eq_iff

      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
  4. Any edge shared between {a, b, c, x} and the remaining family must belong to some block q ∈ P distinct from {a, b, c}.

    To show disjointness, suppose for contradiction that an edge z belongs to the complete graph on {a, b, c, x} and also to the union of edges of P \ {{a, b, c}}. By definition of the union, z must belong to some block q in P \ {{a, b, c}}, meaning q ∈ P and q ≠ {a, b, c}.

    lines 37–41

    uses Finset.disjoint_left.mpr, Finset.mem_biUnion.mp, Finset.mem_erase.mp

      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
  5. The candidate shared edge z is either an edge on {a, b, c} or one of the three spokes to x.

    By in700_four_edges_subset, the edges on {a, b, c, x} are covered by the edges on {a, b, c} and the three spokes {s(a, x), s(b, x), s(c, x)}. We split the contradiction into these two alternatives.

    lines 42–43

    uses in700_four_edges_subset, Finset.mem_union.mp

      have hor := in700_four_edges_subset a b c x hz
      rcases Finset.mem_union.mp hor with hzold | hzspoke
  6. The candidate edge z cannot be an edge on {a, b, c}.

    Since P is pairwise edge-disjoint, the distinct blocks q and {a, b, c} in P intersect in at most one vertex. By in700_encoding_disjoint, their edge encodings are disjoint, contradicting the fact that z belongs to both.

    lines 44–45

    uses in700_encoding_disjoint, Finset.disjoint_left.mp

      · have hd := in700_encoding_disjoint q {a,b,c} (hdisj hqP hp hneq)
        exact Finset.disjoint_left.mp hd hzq hzold
  7. The candidate edge z cannot be any of the three spokes to x.

    If z is a spoke to x, then because z is an edge of q and q ∈ P, z belongs to the union of all block edges in P. This directly contradicts the hypothesis hfree, which states that no spoke belongs to any block of P.

    lines 46–47

    uses Finset.mem_biUnion.mpr

      · apply hfree z hzspoke
        exact Finset.mem_biUnion.mpr ⟨q,hqP,hzq⟩
  8. The main theorem holds: the edges on {a, b, c, x} avoid all edges in the remaining blocks of P.

    The theorem statement is identical to in700_old_edges_disjoint_four, so applying that lemma directly closes the goal.

    line 58

    uses In700Old.in700_old_edges_disjoint_four

      exact In700Old.in700_old_edges_disjoint_four P a b c x hdisj hp hfree
Finset.disjoint_left.mpr
Two 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 all pairs of the form s(x, y).
Finset.mem_filter
An element is in a filtered set if and only if it is in the original set and satisfies the predicate.
Finset.mk_mem_sym2_iff
An unordered pair s(a, b) belongs to the symmetric square of s if and only if both a and b belong to s.
Sym2.isDiag_iff_proj_eq
An unordered pair s(x, y) is on the diagonal (a self-loop) if and only if x = y.
Finset.mem_inter.mpr
If an element belongs to both s and t, it belongs to their intersection s ∩ t.
Finset.one_lt_card.mpr
A finite set containing at least two distinct elements has cardinality strictly greater than 1.
Sym2.mk_isDiag_iff
An unordered pair s(x, y) is on the diagonal if and only if x = y.
Finset.mem_insert
An element is in insert b s if and only if it equals b or is in s.
Finset.mem_singleton
An element is in the singleton set {a} if and only if it equals a.
Finset.mem_union
An element is in the union s ∪ t if and only if it is in s or in t.
Sym2.eq_iff
Two unordered pairs s(x, y) and s(z, w) are equal if and only if their endpoints match in either order.
Finset.mem_biUnion.mp
If an element belongs to a family union, there exists an index block in the family containing it.
Finset.mem_erase
If an element is in s with a erased, it is in s and is not equal to a.
in700_four_edges_subset
The edges on the vertex set {a, b, c, x} are a subset of the edges on {a, b, c} together with the three spokes s(a, x), s(b, x), s(c, x).
Finset.mem_union.mp
If an element is in s ∪ t, it is in s or in t.
in700_encoding_disjoint
If two vertex sets intersect in at most one vertex, their complete graphs are edge-disjoint.
Finset.disjoint_left.mp
If two sets are disjoint, any element in the first does not belong to the second.
Finset.mem_biUnion.mpr
If an element belongs to the image of some index in a family, it belongs to the union over that family.
In700Old.in700_old_edges_disjoint_four
In an edge-disjoint family P containing {a, b, c} whose union avoids the three spokes to x, removing {a, b, c} leaves a family whose edges avoid every edge on {a, b, c, x}.

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

open scoped Sym2namespace In700Oldlemma 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_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⟩end In700Oldtheorem finite_packing_k4_old_edges_avoid {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  exact In700Old.in700_old_edges_disjoint_four P a b c x hdisj hp hfree
See it in the graphDiscuss this resultChallenge it