finite_packing_k4_old_edges_avoid
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
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
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.
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.
uses
Finset.disjoint_left.mpr,Sym2.ind,Finset.mem_filter,Finset.mk_mem_sym2_iff,Sym2.isDiag_iff_proj_eqclassical 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
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.
uses
Finset.mem_inter.mpr,Finset.one_lt_card.mprhave 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
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.
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_iffclassical 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
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}.
uses
Finset.disjoint_left.mpr,Finset.mem_biUnion.mp,Finset.mem_erase.mpclassical 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
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.
uses
in700_four_edges_subset,Finset.mem_union.mphave hor := in700_four_edges_subset a b c x hz rcases Finset.mem_union.mp hor with hzold | hzspoke
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.
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
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.
uses
Finset.mem_biUnion.mpr· apply hfree z hzspoke exact Finset.mem_biUnion.mpr ⟨q,hqP,hzq⟩
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.
uses
In700Old.in700_old_edges_disjoint_fourexact 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}.
- The formalization represents undirected edges as elements of the symmetric square Sym2 V without self-loops (the diagonal), corresponding to the complete graph on a vertex set.
- In lemma in700_four_edges_subset (step 3), the fact that every edge on {a, b, c, x} is either an edge on {a, b, c} or one of the three spokes is verified automatically by aesop through case analysis on the endpoints.
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.
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