simple_graph_forced_k4_face_pivot_retains_forcing
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
- simple_graph_triangle_edge_familyThe family of three-edge sets of all triangles of a finite simple graph.
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- Used by 1
- simple_graph_maximum_packing_two_forced_edges_k4For a maximum triangle packing, if a packed triangle has two singleton-forced edges then its three vertices have a common fourth vertex…
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.
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.
uses
Finset.disjoint_left.mpr,Sym2.ind,Finset.one_lt_card.mprclassical 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
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.
uses
Sym2.indclassical 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
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.
uses
in700_encoding_three,Finset.mem_biUnion.mpr,Finset.mem_image.mprclassical 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]
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.
uses
Sym2.indclassical 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
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}}.
uses
in700_four_edges_subset,in700_encoding_disjoint,Finset.disjoint_left.mp,Finset.mem_biUnion.mprclassical 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⟩
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.
uses
Finset.card_insert_le,Finset.card_singletonhave 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
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.
uses
Finset.one_lt_card.mp,Finset.disjoint_left.mpclassical 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
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.
uses
Finset.mem_sym2_iffintro 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)
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.
uses
Finset.card_singleton,Finset.card_insert_of_notMemhave 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]
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.
refine ⟨?_,hcard⟩ intro u hu v hv hne exact hK.1 (hsub hu) (hsub hv) hne
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.
uses
in700_four_distinct,in700_old_edges_disjoint_four,in700_encoding_monoclassical 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⟩
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|.
uses
in700_clique_subset,in700_card_three,Finset.card_insert_of_notMem,Finset.card_erase_of_memhave 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
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.
uses
in700_encoding_disjoint_iff,Finset.mem_of_mem_erasehave 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
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).
uses
Sym2.eq_swap,Finset.mem_insert_selfhave 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]⟩
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.
uses
in700_clique_subset,in700_card_three,in700_encoding_three,in700_triangle_witnesshave 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'
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.
uses
In700.in700_mainexact 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.
- Steps 2 and 4 rely on the aesop automated tactic to check finite case exhaustion on pairs of vertices.
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.
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