simple_graph_maximum_packing_two_forced_edges_k4
For a maximum triangle packing, if a packed triangle has two singleton-forced edges then its three vertices have a common fourth vertex forming a four-clique, none of the three new spokes is a packing edge, and all three packed edges are singleton-forced. Hence a packed triangle has 0, 1, or 3 singleton-forced edges, never exactly 2.
Statement
theorem simple_graph_maximum_packing_two_forced_edges_k4 (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (p : Finset (Fin n)) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : p ∈ P) (hmarked : 2 ≤ (finite_vertex_set_edge_encoding p ∩ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card) : ∃ x : Fin n, x ∉ p ∧ G.IsNClique 4 (insert x p) ∧ (∀ v ∈ p, s(x,v) ∉ P.biUnion finite_vertex_set_edge_encoding) ∧ finite_vertex_set_edge_encoding p ⊆ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)
- Source
- Local private-witness K4 structure in https://arxiv.org/abs/2001.00257, Section 3; the two-forced-edge formulation is used as a bridge for the triangle-packing campaign.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
- 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.
- finite_maximum_packing_private_witnesses_intersectIn a finite set family with nonempty members, if P is a maximum pairwise-disjoint packing and two family members each avoid every member…
- finite_vertex_family_edge_packing_cover_bridgeEncoding each member of a finite vertex-set family of size at least two by its non-diagonal pairs preserves the family size, converts…
- simple_graph_forced_k4_face_pivot_retains_forcingIf 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 proof, explained
In a maximum triangle packing, if a packed triangle p has two singleton-forced edges, their private witness triangles cannot be edge-disjoint, for otherwise replacing p with both witnesses would yield a larger packing. Since the witnesses only share the packed triangle's vertices and non-packed edges, their third vertices must coincide, creating a fourth vertex x that forms a K₄ with p. None of the three edges connecting x to p is packed, which in turn witnesses that all three edges of p are singleton-forced.
Pull back any pairwise edge-disjoint triangle family Q to a family of 3-cliques R in G.
Given a collection Q of edge-disjoint triangle edge sets, we define R to be the set of 3-cliques whose edge encodings belong to Q. Each member of R is a 3-clique and therefore has cardinality at least 2.
classical intro Q hQ hQdis let Tall : Finset (Finset V) := Finset.univ.filter (G.IsNClique 3) let R : Finset (Finset V) := Tall.filter (fun t => finite_vertex_set_edge_encoding t ∈ Q) have hRtri : ∀ t ∈ R, G.IsNClique 3 t := by intro t ht exact (Finset.mem_filter.mp (Finset.mem_filter.mp ht).1).2 have hRsize : ∀ t ∈ R, 2 ≤ t.card := by intro t ht have h := (hRtri t ht).card_eq omega
The family R is an edge-disjoint triangle packing of vertices with the same cardinality as Q.
The edge encoding maps R bijectively onto Q. Using the bridge lemma finite_vertex_family_edge_packing_cover_bridge, pairwise disjointness of Q in edges translates to pairwise intersection of size at most 1 in vertices, so |Q| = |R|.
uses
finite_vertex_family_edge_packing_cover_bridgehave himage : R.image finite_vertex_set_edge_encoding = Q := by ext e constructor · intro he obtain ⟨t,ht,rfl⟩ := Finset.mem_image.mp he exact (Finset.mem_filter.mp ht).2 · intro he have he' := hQ he change e ∈ Tall.image finite_vertex_set_edge_encoding at he' obtain ⟨t,ht,rfl⟩ := Finset.mem_image.mp he' exact Finset.mem_image.mpr ⟨t,Finset.mem_filter.mpr ⟨ht,he⟩,rfl⟩ have hRbridge := finite_vertex_family_edge_packing_cover_bridge R (∅ : Finset (Sym2 V)) hRsize (by simp) have hRdis : (R : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by apply hRbridge.2.1.mp simpa [himage] using hQdis have hRcard : Q.card = R.card := by rw [← himage]; exact hRbridge.1
The size of Q is at most the size of the packed edge family of P.
Since R is a valid triangle packing, its size is bounded by the triangle packing number of G. Since P achieves this maximum, |Q| = |R| ≤ |P| = |P.image finite_vertex_set_edge_encoding|.
uses
finite_vertex_family_edge_packing_cover_bridgehave hRbound : R.card ≤ simple_graph_triangle_packing_number G := by unfold simple_graph_triangle_packing_number apply le_csSup · refine ⟨Fintype.card (Finset V), ?_⟩ rintro k ⟨T,_,_,rfl⟩ exact Finset.card_le_univ T · exact ⟨R,hRtri,hRdis,rfl⟩ have hPsize : ∀ t ∈ P, 2 ≤ t.card := by intro t ht have h := (htri t ht).card_eq omega have hPbridge := finite_vertex_family_edge_packing_cover_bridge P (∅ : Finset (Sym2 V)) hPsize (by simp) rw [hPbridge.1,hRcard,hmax] exact hRbound
The edge sets of triangles in P form a maximum edge packing Q in the triangle edge family.
We define F as the family of all triangle edge sets and Q as the image of P under edge encoding. Using family_max and the bridge lemma, Q is a pairwise disjoint family of non-empty edge sets of maximum size in F.
uses
family_max,finite_vertex_family_edge_packing_cover_bridgeclassical let F := simple_graph_triangle_edge_family G let Q := P.image finite_vertex_set_edge_encoding have hnonempty : ∀ t ∈ F, t.Nonempty := by intro t ht obtain ⟨s,hs,rfl⟩ := Finset.mem_image.mp ht have hscl : G.IsNClique 3 s := (Finset.mem_filter.mp hs).2 obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp hscl.card_eq refine ⟨s(a,b), ?_⟩ simp [finite_vertex_set_edge_encoding, hab] have hQF : Q ⊆ F := by intro t ht obtain ⟨s,hs,rfl⟩ := Finset.mem_image.mp ht exact Finset.mem_image.mpr ⟨s,Finset.mem_filter.mpr ⟨Finset.mem_univ _,htri s hs⟩,rfl⟩ have hPsize : ∀ t ∈ P, 2 ≤ t.card := by intro t ht have h := (htri t ht).card_eq omega have hQdis : (Q : Set (Finset (Sym2 V))).Pairwise Disjoint := (finite_vertex_family_edge_packing_cover_bridge P (∅ : Finset (Sym2 V)) hPsize (by simp)).2.1.mpr hdisj have hQmax : ∀ R : Finset (Finset (Sym2 V)), R ⊆ F → (R : Set (Finset (Sym2 V))).Pairwise Disjoint → R.card ≤ Q.card := family_max G P htri hdisj hmax
Any two triangles whose packed edges are contained in p cannot be edge-disjoint.
Both witness triangles T and U are private to p, meaning they are edge-disjoint from every other triangle in P. By finite_maximum_packing_private_witnesses_intersect, if T and U were edge-disjoint, replacing p with both T and U would produce a strictly larger packing, contradicting maximality.
uses
finite_maximum_packing_private_witnesses_intersecthave hprivate (T : Finset (Sym2 V)) (htp : ∀ e ∈ T, e ∈ P.biUnion finite_vertex_set_edge_encoding → e ∈ finite_vertex_set_edge_encoding p) : ∀ q ∈ Q, q ≠ finite_vertex_set_edge_encoding p → Disjoint q T := by intro q hq hne obtain ⟨r,hr,rfl⟩ := Finset.mem_image.mp hq apply Finset.disjoint_left.mpr intro e her heT have heU : e ∈ P.biUnion finite_vertex_set_edge_encoding := Finset.mem_biUnion.mpr ⟨r,hr,her⟩ have hep := htp e heT heU exact Finset.disjoint_left.mp (hQdis (Finset.mem_image.mpr ⟨r,hr,rfl⟩) (Finset.mem_image.mpr ⟨p,hp,rfl⟩) hne) her hep exact finite_maximum_packing_private_witnesses_intersect F Q hnonempty hQF hQdis hQmax (finite_vertex_set_edge_encoding p) T U hT hU (hprivate T hTp) (hprivate U hUp)
Any two distinct vertices in a 3-element set determine the third vertex.
Given T with |T| = 3 and distinct elements a, b ∈ T, case analysis on the three elements of T produces a unique third vertex x distinct from both a and b such that T = {a, b, x}.
uses
Finset.card_eq_three.mpobtain ⟨u,v,w,huv,huw,hvw,rfl⟩ := Finset.card_eq_three.mp hT simp only [Finset.mem_insert,Finset.mem_singleton] at ha hb rcases ha with rfl | rfl | rfl <;> rcases hb with rfl | rfl | rfl all_goals simp_all all_goals first | exact ⟨u, by aesop, by aesop, by ext z; simp <;> tauto⟩ | exact ⟨v, by aesop, by aesop, by ext z; simp <;> tauto⟩ | exact ⟨w, by aesop, by aesop, by ext z; simp <;> tauto⟩
A singleton-forced edge has a witness triangle meeting the packed edges in that edge alone.
By definition of being singleton-forced, the edge e belongs to a triangle whose edge set intersects the set of packed edges in a singleton; this singleton must be {e}.
classical obtain ⟨F,hF,heF⟩ := Finset.mem_biUnion.mp he obtain ⟨hFG,hFcard⟩ := Finset.mem_filter.mp hF obtain ⟨T,hTG,rfl⟩ := Finset.mem_image.mp hFG have hT : G.IsNClique 3 T := (Finset.mem_filter.mp hTG).2 obtain ⟨z,hz⟩ := Finset.card_eq_one.mp hFcard have hez : e = z := by have : e ∈ finite_vertex_set_edge_encoding T ∩ P.biUnion finite_vertex_set_edge_encoding := Finset.mem_inter.mpr ⟨heF,hePacked⟩ simpa [hz] using this subst z exact ⟨T,hT,heF,hz⟩
The singleton-forced edges {a, b} and {a, c} have witness triangles {a, b, x} and {a, c, y}.
We apply witness_at_edge to {a, b} and {a, c} to obtain witness triangles T and U, and then triangle_third to express them as {a, b, x} and {a, c, y}.
uses
witness_at_edge,triangle_thirdclassical let W := P.biUnion finite_vertex_set_edge_encoding have hPacked (e : Sym2 V) (he : e ∈ finite_vertex_set_edge_encoding ({a,b,c} : Finset V)) : e ∈ W := Finset.mem_biUnion.mpr ⟨{a,b,c},hp,he⟩ have habP : s(a,b) ∈ W := hPacked _ (by simp [finite_vertex_set_edge_encoding,hab]) have hacP : s(a,c) ∈ W := hPacked _ (by simp [finite_vertex_set_edge_encoding,hac]) have hbcP : s(b,c) ∈ W := hPacked _ (by simp [finite_vertex_set_edge_encoding,hbc]) obtain ⟨T,hTG,heT,hTcap⟩ := witness_at_edge G P s(a,b) habP hAB obtain ⟨U,hUG,heU,hUcap⟩ := witness_at_edge G P s(a,c) hacP hAC have hmT : a ∈ T ∧ b ∈ T := by simpa [finite_vertex_set_edge_encoding,hab] using heT have hmU : a ∈ U ∧ c ∈ U := by simpa [finite_vertex_set_edge_encoding,hac] using heU obtain ⟨x,hxa,hxb,hT⟩ := triangle_third T a b hTG.card_eq hmT.1 hmT.2 hab obtain ⟨y,hya,hyc,hU⟩ := triangle_third U a c hUG.card_eq hmU.1 hmU.2 hac subst T subst U
The witness triangles {a, b, x} and {a, c, y} contain no packed edges outside {a, b, c}.
Neither x = c nor y = b can hold, as that would introduce a second packed edge into T or U. Consequently, every packed edge of {a, b, x} is {a, b} and every packed edge of {a, c, y} is {a, c}, so both are private to {a, b, c}.
have hxc : x ≠ c := by intro h; subst x have hx : s(a,c) ∈ finite_vertex_set_edge_encoding ({a,b,c} : Finset V) ∩ W := Finset.mem_inter.mpr ⟨by simp [finite_vertex_set_edge_encoding,hac],hacP⟩ rw [hTcap] at hx simp only [Finset.mem_singleton, Sym2.eq_iff] at hx aesop have hyb : y ≠ b := by intro h; subst y have hx : s(a,b) ∈ finite_vertex_set_edge_encoding ({a,c,b} : Finset V) ∩ W := Finset.mem_inter.mpr ⟨by simp [finite_vertex_set_edge_encoding,hab],habP⟩ rw [hUcap] at hx simp only [Finset.mem_singleton, Sym2.eq_iff] at hx aesop have hTp : ∀ e ∈ finite_vertex_set_edge_encoding ({a,b,x} : Finset V), e ∈ W → e ∈ finite_vertex_set_edge_encoding ({a,b,c} : Finset V) := by intro e he heW have hh : e ∈ ({s(a,b)} : Finset (Sym2 V)) := by rw [← hTcap]; exact Finset.mem_inter.mpr ⟨he,heW⟩ have : e = s(a,b) := Finset.mem_singleton.mp hh subst e simp [finite_vertex_set_edge_encoding,hab] have hUp : ∀ e ∈ finite_vertex_set_edge_encoding ({a,c,y} : Finset V), e ∈ W → e ∈ finite_vertex_set_edge_encoding ({a,b,c} : Finset V) := by intro e he heW have hh : e ∈ ({s(a,c)} : Finset (Sym2 V)) := by rw [← hUcap]; exact Finset.mem_inter.mpr ⟨he,heW⟩ have : e = s(a,c) := Finset.mem_singleton.mp hh subst e simp [finite_vertex_set_edge_encoding,hac] have hTF : finite_vertex_set_edge_encoding ({a,b,x} : Finset V) ∈ simple_graph_triangle_edge_family G := by exact Finset.mem_image.mpr ⟨{a,b,x},Finset.mem_filter.mpr ⟨Finset.mem_univ _,hTG⟩,rfl⟩ have hUF : finite_vertex_set_edge_encoding ({a,c,y} : Finset V) ∈ simple_graph_triangle_edge_family G := by exact Finset.mem_image.mpr ⟨{a,c,y},Finset.mem_filter.mpr ⟨Finset.mem_univ _,hUG⟩,rfl⟩
The two witness triangles share the same third vertex, so x = y.
By witnesses_meet, the witness triangles T and U must share an edge. Testing all pairs of edges between {a, b, x} and {a, c, y}, the only edge they can possibly share is the edge incident to a and the third vertex, which forces x = y.
uses
witnesses_meethave hmeet := witnesses_meet G P htri hdisj hmax {a,b,c} hp _ _ hTF hUF hTp hUp have hxy : x = y := by by_contra hxy apply hmeet rw [In700.in700_encoding_three a b x hab (Ne.symm hxa) (Ne.symm hxb), In700.in700_encoding_three a c y hac (Ne.symm hya) (Ne.symm hyc)] simp only [Finset.disjoint_left, Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff] aesop subst y
None of the three spoke edges {a, x}, {b, x}, {c, x} is a packed edge.
If any spoke were a packed edge, it would belong to the intersection of T or U with the packed edges, which is restricted to {a, b} or {a, c}.
have hfreeAX : s(a,x) ∉ W := by intro he have hh : s(a,x) ∈ ({s(a,b)} : Finset (Sym2 V)) := by rw [← hTcap]; exact Finset.mem_inter.mpr ⟨by simp [finite_vertex_set_edge_encoding,Ne.symm hxa],he⟩ simp only [Finset.mem_singleton,Sym2.eq_iff] at hh aesop have hfreeBX : s(b,x) ∉ W := by intro he have hh : s(b,x) ∈ ({s(a,b)} : Finset (Sym2 V)) := by rw [← hTcap]; exact Finset.mem_inter.mpr ⟨by simp [finite_vertex_set_edge_encoding,Ne.symm hxb],he⟩ simp only [Finset.mem_singleton,Sym2.eq_iff] at hh aesop have hfreeCX : s(c,x) ∉ W := by intro he have hh : s(c,x) ∈ ({s(a,c)} : Finset (Sym2 V)) := by rw [← hUcap]; exact Finset.mem_inter.mpr ⟨by simp [finite_vertex_set_edge_encoding,Ne.symm hxc],he⟩ simp only [Finset.mem_singleton,Sym2.eq_iff] at hh aesop
The vertices a, b, c, x form a 4-clique with non-packed spokes.
Since {a, b, c} is a triangle in P, and {a, b, x} and {a, c, x} are cliques in G, all pairs among {a, b, c, x} are adjacent. Furthermore, x ∉ {a, b, c}, so the set has size 4 and forms a K₄.
refine ⟨x,by simp [hxa,hxb,hxc],?_,?_⟩ · constructor · have habG : G.Adj a b := (htri _ hp).1 (by simp) (by simp) hab have hacG : G.Adj a c := (htri _ hp).1 (by simp) (by simp) hac have hbcG : G.Adj b c := (htri _ hp).1 (by simp) (by simp) hbc have haxG : G.Adj a x := hTG.1 (by simp) (by simp) (Ne.symm hxa) have hbxG : G.Adj b x := hTG.1 (by simp) (by simp) (Ne.symm hxb) have hcxG : G.Adj c x := hUG.1 (by simp) (by simp) (Ne.symm hxc) intro u hu v hv huv simp only [Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton] at hu hv rcases hu with rfl | rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl | rfl all_goals first | contradiction | assumption | exact SimpleGraph.Adj.symm (by assumption) · have heq : ({a,b,c,x} : Finset V) = insert x {a,b,c} := by ext z simp only [Finset.mem_insert,Finset.mem_singleton] tauto rw [heq,Finset.card_insert_of_notMem (by simp [hxa,hxb,hxc]), In700.in700_card_three hab hac hbc] · intro v hv simp only [Finset.mem_insert,Finset.mem_singleton] at hv rcases hv with rfl | rfl | rfl · simpa only [Sym2.eq_swap] using hfreeAX · simpa only [Sym2.eq_swap] using hfreeBX · simpa only [Sym2.eq_swap] using hfreeCX
If a packed triangle forms a K₄ with non-packed spokes, all three of its edges are singleton-forced.
For each edge of {a, b, c}, the triangle formed with x has that edge as its only packed edge because the two spokes to x are not packed. Thus, all three edges are witnessed to be singleton-forced.
classical have hxa : x ≠ a := by intro h; subst x; exact hx (by simp) have hxb : x ≠ b := by intro h; subst x; exact hx (by simp) have hxc : x ≠ c := by intro h; subst x; exact hx (by simp) let W := P.biUnion finite_vertex_set_edge_encoding have hPacked (e : Sym2 V) (he : e ∈ finite_vertex_set_edge_encoding ({a,b,c} : Finset V)) : e ∈ W := Finset.mem_biUnion.mpr ⟨{a,b,c},hp,he⟩ have hfa : s(a,x) ∉ W := by simpa only [Sym2.eq_swap] using hfree a (by simp) have hfb : s(b,x) ∉ W := by simpa only [Sym2.eq_swap] using hfree b (by simp) have hfc : s(c,x) ∉ W := by simpa only [Sym2.eq_swap] using hfree c (by simp) have ht (u v : V) (hu : u ∈ ({a,b,c} : Finset V)) (hv : v ∈ ({a,b,c} : Finset V)) (huv : u ≠ v) (hux : u ≠ x) (hvx : v ≠ x) : G.IsNClique 3 ({u,v,x} : Finset V) := by apply In700.in700_clique_subset G {a,b,c,x} {u,v,x} hk4 · intro z hz simp only [Finset.mem_insert,Finset.mem_singleton] at hz ⊢ simp only [Finset.mem_insert,Finset.mem_singleton] at hu hv aesop · exact In700.in700_card_three huv hux hvx have hab' := In700.in700_triangle_witness G W a b x hab (Ne.symm hxa) (Ne.symm hxb) (ht a b (by simp) (by simp) hab (Ne.symm hxa) (Ne.symm hxb)) (hPacked _ (by simp [finite_vertex_set_edge_encoding,hab])) hfb (by simpa only [Sym2.eq_swap] using hfa) have hbc' := In700.in700_triangle_witness G W b c x hbc (Ne.symm hxb) (Ne.symm hxc) (ht b c (by simp) (by simp) hbc (Ne.symm hxb) (Ne.symm hxc)) (hPacked _ (by simp [finite_vertex_set_edge_encoding,hbc])) hfc (by simpa only [Sym2.eq_swap] using hfb) have hca' := In700.in700_triangle_witness G W c a x (Ne.symm hac) (Ne.symm hxc) (Ne.symm hxa) (ht c a (by simp) (by simp) (Ne.symm hac) (Ne.symm hxc) (Ne.symm hxa)) (hPacked _ (by simp [finite_vertex_set_edge_encoding,Ne.symm hac])) hfa (by simpa only [Sym2.eq_swap] using hfc) rw [In700.in700_encoding_three a b c hab hac hbc] intro e he simp only [Finset.mem_insert,Finset.mem_singleton] at he rcases he with rfl | rfl | rfl <;> assumption
If at least two edges of a triangle are forced, two of them share a vertex.
Since at least two of the three edges belong to the set of forced edges, case analysis over the pairs of edges shows that they must share an endpoint: either at a, at b, or at c.
(s(a,b) ∈ F ∧ s(a,c) ∈ F) ∨ (s(b,a) ∈ F ∧ s(b,c) ∈ F) ∨ (s(c,a) ∈ F ∧ s(c,b) ∈ F) := by have hmany : 1 < (finite_vertex_set_edge_encoding ({a,b,c} : Finset V) ∩ F).card := by omega obtain ⟨e,he,f,hf,hef⟩ := Finset.one_lt_card.mp hmany have heF : e ∈ F := (Finset.mem_inter.mp he).2 have hfF : f ∈ F := (Finset.mem_inter.mp hf).2 have heE := (Finset.mem_inter.mp he).1 have hfE := (Finset.mem_inter.mp hf).1 rw [In700.in700_encoding_three a b c hab hac hbc] at heE hfE simp only [Finset.mem_insert,Finset.mem_singleton] at heE hfE rcases heE with heE | heE | heE · subst e rcases hfE with hfE | hfE | hfE · subst f; exact (hef rfl).elim · subst f; right; left; exact ⟨by simpa only [Sym2.eq_swap] using heF,hfF⟩ · subst f; left; exact ⟨heF,by simpa only [Sym2.eq_swap] using hfF⟩ · subst e rcases hfE with hfE | hfE | hfE · subst f; right; left; exact ⟨by simpa only [Sym2.eq_swap] using hfF,heF⟩ · subst f; exact (hef rfl).elim · subst f; right; right; exact ⟨hfF, by simpa only [Sym2.eq_swap] using heF⟩ · subst e rcases hfE with hfE | hfE | hfE · subst f; left; exact ⟨hfF,by simpa only [Sym2.eq_swap] using heF⟩The existence of the K₄ holds in all three symmetric cases.
We apply two_edges_ordered when the two forced edges meet at a, and apply it after permuting the vertices when they meet at b or c.
uses
two_edges_orderedclassical rcases hchoose with ⟨h1,h2⟩ | ⟨h1,h2⟩ | ⟨h1,h2⟩ · exact two_edges_ordered G P htri hdisj hmax a b c hab hac hbc hp h1 h2 · have hperm : ({b,a,c} : Finset (Fin n)) = {a,b,c} := by ext z; simp only [Finset.mem_insert,Finset.mem_singleton]; tauto have hperm4 (x : Fin n) : ({b,a,c,x} : Finset (Fin n)) = {a,b,c,x} := by ext z; simp only [Finset.mem_insert,Finset.mem_singleton]; tauto have hp' : ({b,a,c} : Finset (Fin n)) ∈ P := by simpa only [hperm] using hp obtain ⟨x,hx,hfour,hfree⟩ := two_edges_ordered G P htri hdisj hmax b a c (Ne.symm hab) hbc hac hp' h1 h2 exact ⟨x,by simpa only [hperm] using hx,by simpa only [hperm4] using hfour,by simpa only [hperm] using hfree⟩ · have hperm : ({c,a,b} : Finset (Fin n)) = {a,b,c} := by ext z; simp only [Finset.mem_insert,Finset.mem_singleton]; tauto have hperm4 (x : Fin n) : ({c,a,b,x} : Finset (Fin n)) = {a,b,c,x} := by ext z; simp only [Finset.mem_insert,Finset.mem_singleton]; tauto have hp' : ({c,a,b} : Finset (Fin n)) ∈ P := by simpa only [hperm] using hp obtain ⟨x,hx,hfour,hfree⟩ := two_edges_ordered G P htri hdisj hmax c a b (Ne.symm hac) (Ne.symm hbc) hab hp' h1 h2 exact ⟨x,by simpa only [hperm] using hx,by simpa only [hperm4] using hfour,by simpa only [hperm] using hfree⟩Inserting x into {a, b, c} equals {a, b, c, x}.
This is a set extensionality identity.
ext z simp only [Finset.mem_insert,Finset.mem_singleton] tauto
For any triangle with at least two forced edges, the K₄ exists and all three edges are forced.
We select two forced edges sharing a vertex via in701_choose, construct the K₄ with non-packed spokes via in701_k4_choose, and conclude all three edges are forced via k4_all_forced.
uses
in701_choose,in701_k4_choose,k4_all_forced,in701_insert_fourclassical let F := (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) have hmarked' : 2 ≤ (finite_vertex_set_edge_encoding ({a,b,c} : Finset (Fin n)) ∩ F).card := hmarked have hchoose := in701_choose a b c hab hac hbc F hmarked' have hK := in701_k4_choose n G P htri hdisj hmax a b c hab hac hbc hp hchoose obtain ⟨x,hx,hfour,hfree⟩ := hK refine ⟨x,hx,?_,hfree,k4_all_forced G P a b c x hab hac hbc hp hx hfour hfree⟩ rw [in701_insert_four] exact hfour
The main theorem holds for any packed triangle with at least two singleton-forced edges.
Since p ∈ P is a 3-clique, we decompose it into three distinct vertices a, b, c and invoke in701_main_ordered.
uses
Finset.card_eq_three.mp,in701_main_orderedclassical obtain ⟨a,b,c,hab,hac,hbc,hpEq⟩ := Finset.card_eq_three.mp (htri p hp).card_eq subst p exact in701_main_ordered n G P htri hdisj hmax a b c hab hac hbc hp hmarked
family_max- An edge packing of triangle edge sets has size bounded by the triangle packing number of the graph.
witnesses_meet- Any two triangle edge sets whose packed edges are contained in a single packed triangle must intersect.
triangle_third- In any 3-element set containing two distinct elements a and b, there is a unique third element x.
witness_at_edge- A singleton-forced packed edge has an explicit witness triangle whose edge set intersects the packed edges in exactly that edge.
two_edges_ordered- If a packed triangle has two singleton-forced edges, there is a fourth vertex forming a K₄ whose spokes are not packed edges.
k4_all_forced- If a packed triangle forms a K₄ with non-packed spokes, all three of its edges are singleton-forced.
in701_choose- If at least two edges of a triangle belong to a set F, then two of those edges share a common vertex.
in701_k4_choose- Reduces the three symmetric choices of two forced edges sharing a vertex to two_edges_ordered.
in701_insert_four- Inserting x into {a, b, c} yields the 4-element set {a, b, c, x}.
in701_main_ordered- For an ordered triangle {a, b, c} with at least two forced edges, the K₄ exists and all three edges are forced.
Finset.card_eq_three.mp- A finite set has cardinality 3 if and only if it consists of three distinct elements.
finite_vertex_family_edge_packing_cover_bridge- Connects packing and covering of vertex families with edge encodings.
finite_maximum_packing_private_witnesses_intersect- In a maximum packing, two private witnesses for the same packed element must intersect.
- Unresolved check: no step explains line(s) 319, 320 -- every tactic of the proof has to belong to some step
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.
Lean’s trace was cut to the first 400 of 489 tactics.
set_option maxHeartbeats 2000000set_option maxRecDepth 10000open scoped Sym2namespace In701lemma family_max {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset V)).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) : ∀ Q : Finset (Finset (Sym2 V)), Q ⊆ simple_graph_triangle_edge_family G → (Q : Set (Finset (Sym2 V))).Pairwise Disjoint → Q.card ≤ (P.image finite_vertex_set_edge_encoding).card := by classical intro Q hQ hQdis let Tall : Finset (Finset V) := Finset.univ.filter (G.IsNClique 3) let R : Finset (Finset V) := Tall.filter (fun t => finite_vertex_set_edge_encoding t ∈ Q) have hRtri : ∀ t ∈ R, G.IsNClique 3 t := by intro t ht exact (Finset.mem_filter.mp (Finset.mem_filter.mp ht).1).2 have hRsize : ∀ t ∈ R, 2 ≤ t.card := by intro t ht have h := (hRtri t ht).card_eq omega have himage : R.image finite_vertex_set_edge_encoding = Q := by ext e constructor · intro he obtain ⟨t,ht,rfl⟩ := Finset.mem_image.mp he exact (Finset.mem_filter.mp ht).2 · intro he have he' := hQ he change e ∈ Tall.image finite_vertex_set_edge_encoding at he' obtain ⟨t,ht,rfl⟩ := Finset.mem_image.mp he' exact Finset.mem_image.mpr ⟨t,Finset.mem_filter.mpr ⟨ht,he⟩,rfl⟩ have hRbridge := finite_vertex_family_edge_packing_cover_bridge R (∅ : Finset (Sym2 V)) hRsize (by simp) have hRdis : (R : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) := by apply hRbridge.2.1.mp simpa [himage] using hQdis have hRcard : Q.card = R.card := by rw [← himage]; exact hRbridge.1 have hRbound : R.card ≤ simple_graph_triangle_packing_number G := by unfold simple_graph_triangle_packing_number apply le_csSup · refine ⟨Fintype.card (Finset V), ?_⟩ rintro k ⟨T,_,_,rfl⟩ exact Finset.card_le_univ T · exact ⟨R,hRtri,hRdis,rfl⟩ have hPsize : ∀ t ∈ P, 2 ≤ t.card := by intro t ht have h := (htri t ht).card_eq omega have hPbridge := finite_vertex_family_edge_packing_cover_bridge P (∅ : Finset (Sym2 V)) hPsize (by simp) rw [hPbridge.1,hRcard,hmax] exact hRboundlemma witnesses_meet {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset V)).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (p : Finset V) (hp : p ∈ P) (T U : Finset (Sym2 V)) (hT : T ∈ simple_graph_triangle_edge_family G) (hU : U ∈ simple_graph_triangle_edge_family G) (hTp : ∀ e ∈ T, e ∈ P.biUnion finite_vertex_set_edge_encoding → e ∈ finite_vertex_set_edge_encoding p) (hUp : ∀ e ∈ U, e ∈ P.biUnion finite_vertex_set_edge_encoding → e ∈ finite_vertex_set_edge_encoding p) : ¬ Disjoint T U := by classical let F := simple_graph_triangle_edge_family G let Q := P.image finite_vertex_set_edge_encoding have hnonempty : ∀ t ∈ F, t.Nonempty := by intro t ht obtain ⟨s,hs,rfl⟩ := Finset.mem_image.mp ht have hscl : G.IsNClique 3 s := (Finset.mem_filter.mp hs).2 obtain ⟨a,b,c,hab,hac,hbc,rfl⟩ := Finset.card_eq_three.mp hscl.card_eq refine ⟨s(a,b), ?_⟩ simp [finite_vertex_set_edge_encoding, hab] have hQF : Q ⊆ F := by intro t ht obtain ⟨s,hs,rfl⟩ := Finset.mem_image.mp ht exact Finset.mem_image.mpr ⟨s,Finset.mem_filter.mpr ⟨Finset.mem_univ _,htri s hs⟩,rfl⟩ have hPsize : ∀ t ∈ P, 2 ≤ t.card := by intro t ht have h := (htri t ht).card_eq omega have hQdis : (Q : Set (Finset (Sym2 V))).Pairwise Disjoint := (finite_vertex_family_edge_packing_cover_bridge P (∅ : Finset (Sym2 V)) hPsize (by simp)).2.1.mpr hdisj have hQmax : ∀ R : Finset (Finset (Sym2 V)), R ⊆ F → (R : Set (Finset (Sym2 V))).Pairwise Disjoint → R.card ≤ Q.card := family_max G P htri hdisj hmax have hprivate (T : Finset (Sym2 V)) (htp : ∀ e ∈ T, e ∈ P.biUnion finite_vertex_set_edge_encoding → e ∈ finite_vertex_set_edge_encoding p) : ∀ q ∈ Q, q ≠ finite_vertex_set_edge_encoding p → Disjoint q T := by intro q hq hne obtain ⟨r,hr,rfl⟩ := Finset.mem_image.mp hq apply Finset.disjoint_left.mpr intro e her heT have heU : e ∈ P.biUnion finite_vertex_set_edge_encoding := Finset.mem_biUnion.mpr ⟨r,hr,her⟩ have hep := htp e heT heU exact Finset.disjoint_left.mp (hQdis (Finset.mem_image.mpr ⟨r,hr,rfl⟩) (Finset.mem_image.mpr ⟨p,hp,rfl⟩) hne) her hep exact finite_maximum_packing_private_witnesses_intersect F Q hnonempty hQF hQdis hQmax (finite_vertex_set_edge_encoding p) T U hT hU (hprivate T hTp) (hprivate U hUp)end In701namespace In701lemma triangle_third {V : Type*} [DecidableEq V] (T : Finset V) (a b : V) (hT : T.card = 3) (ha : a ∈ T) (hb : b ∈ T) (hab : a ≠ b) : ∃ x, x ≠ a ∧ x ≠ b ∧ T = {a,b,x} := by obtain ⟨u,v,w,huv,huw,hvw,rfl⟩ := Finset.card_eq_three.mp hT simp only [Finset.mem_insert,Finset.mem_singleton] at ha hb rcases ha with rfl | rfl | rfl <;> rcases hb with rfl | rfl | rfl all_goals simp_all all_goals first | exact ⟨u, by aesop, by aesop, by ext z; simp <;> tauto⟩ | exact ⟨v, by aesop, by aesop, by ext z; simp <;> tauto⟩ | exact ⟨w, by aesop, by aesop, by ext z; simp <;> tauto⟩lemma witness_at_edge {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (e : Sym2 V) (hePacked : e ∈ P.biUnion finite_vertex_set_edge_encoding) (he : e ∈ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)) : ∃ T : Finset V, G.IsNClique 3 T ∧ e ∈ finite_vertex_set_edge_encoding T ∧ finite_vertex_set_edge_encoding T ∩ P.biUnion finite_vertex_set_edge_encoding = {e} := by classical obtain ⟨F,hF,heF⟩ := Finset.mem_biUnion.mp he obtain ⟨hFG,hFcard⟩ := Finset.mem_filter.mp hF obtain ⟨T,hTG,rfl⟩ := Finset.mem_image.mp hFG have hT : G.IsNClique 3 T := (Finset.mem_filter.mp hTG).2 obtain ⟨z,hz⟩ := Finset.card_eq_one.mp hFcard have hez : e = z := by have : e ∈ finite_vertex_set_edge_encoding T ∩ P.biUnion finite_vertex_set_edge_encoding := Finset.mem_inter.mpr ⟨heF,hePacked⟩ simpa [hz] using this subst z exact ⟨T,hT,heF,hz⟩end In701namespace In701lemma two_edges_ordered {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset V)).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (a b c : V) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (hp : ({a,b,c} : Finset V) ∈ P) (hAB : s(a,b) ∈ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)) (hAC : s(a,c) ∈ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)) : ∃ x, x ∉ ({a,b,c} : Finset V) ∧ G.IsNClique 4 ({a,b,c,x} : Finset V) ∧ (∀ v ∈ ({a,b,c} : Finset V), s(x,v) ∉ P.biUnion finite_vertex_set_edge_encoding) := by classical let W := P.biUnion finite_vertex_set_edge_encoding have hPacked (e : Sym2 V) (he : e ∈ finite_vertex_set_edge_encoding ({a,b,c} : Finset V)) : e ∈ W := Finset.mem_biUnion.mpr ⟨{a,b,c},hp,he⟩ have habP : s(a,b) ∈ W := hPacked _ (by simp [finite_vertex_set_edge_encoding,hab]) have hacP : s(a,c) ∈ W := hPacked _ (by simp [finite_vertex_set_edge_encoding,hac]) have hbcP : s(b,c) ∈ W := hPacked _ (by simp [finite_vertex_set_edge_encoding,hbc]) obtain ⟨T,hTG,heT,hTcap⟩ := witness_at_edge G P s(a,b) habP hAB obtain ⟨U,hUG,heU,hUcap⟩ := witness_at_edge G P s(a,c) hacP hAC have hmT : a ∈ T ∧ b ∈ T := by simpa [finite_vertex_set_edge_encoding,hab] using heT have hmU : a ∈ U ∧ c ∈ U := by simpa [finite_vertex_set_edge_encoding,hac] using heU obtain ⟨x,hxa,hxb,hT⟩ := triangle_third T a b hTG.card_eq hmT.1 hmT.2 hab obtain ⟨y,hya,hyc,hU⟩ := triangle_third U a c hUG.card_eq hmU.1 hmU.2 hac subst T subst U have hxc : x ≠ c := by intro h; subst x have hx : s(a,c) ∈ finite_vertex_set_edge_encoding ({a,b,c} : Finset V) ∩ W := Finset.mem_inter.mpr ⟨by simp [finite_vertex_set_edge_encoding,hac],hacP⟩ rw [hTcap] at hx simp only [Finset.mem_singleton, Sym2.eq_iff] at hx aesop have hyb : y ≠ b := by intro h; subst y have hx : s(a,b) ∈ finite_vertex_set_edge_encoding ({a,c,b} : Finset V) ∩ W := Finset.mem_inter.mpr ⟨by simp [finite_vertex_set_edge_encoding,hab],habP⟩ rw [hUcap] at hx simp only [Finset.mem_singleton, Sym2.eq_iff] at hx aesop have hTp : ∀ e ∈ finite_vertex_set_edge_encoding ({a,b,x} : Finset V), e ∈ W → e ∈ finite_vertex_set_edge_encoding ({a,b,c} : Finset V) := by intro e he heW have hh : e ∈ ({s(a,b)} : Finset (Sym2 V)) := by rw [← hTcap]; exact Finset.mem_inter.mpr ⟨he,heW⟩ have : e = s(a,b) := Finset.mem_singleton.mp hh subst e simp [finite_vertex_set_edge_encoding,hab] have hUp : ∀ e ∈ finite_vertex_set_edge_encoding ({a,c,y} : Finset V), e ∈ W → e ∈ finite_vertex_set_edge_encoding ({a,b,c} : Finset V) := by intro e he heW have hh : e ∈ ({s(a,c)} : Finset (Sym2 V)) := by rw [← hUcap]; exact Finset.mem_inter.mpr ⟨he,heW⟩ have : e = s(a,c) := Finset.mem_singleton.mp hh subst e simp [finite_vertex_set_edge_encoding,hac] have hTF : finite_vertex_set_edge_encoding ({a,b,x} : Finset V) ∈ simple_graph_triangle_edge_family G := by exact Finset.mem_image.mpr ⟨{a,b,x},Finset.mem_filter.mpr ⟨Finset.mem_univ _,hTG⟩,rfl⟩ have hUF : finite_vertex_set_edge_encoding ({a,c,y} : Finset V) ∈ simple_graph_triangle_edge_family G := by exact Finset.mem_image.mpr ⟨{a,c,y},Finset.mem_filter.mpr ⟨Finset.mem_univ _,hUG⟩,rfl⟩ have hmeet := witnesses_meet G P htri hdisj hmax {a,b,c} hp _ _ hTF hUF hTp hUp have hxy : x = y := by by_contra hxy apply hmeet rw [In700.in700_encoding_three a b x hab (Ne.symm hxa) (Ne.symm hxb), In700.in700_encoding_three a c y hac (Ne.symm hya) (Ne.symm hyc)] simp only [Finset.disjoint_left, Finset.mem_insert, Finset.mem_singleton, Sym2.eq_iff] aesop subst y have hfreeAX : s(a,x) ∉ W := by intro he have hh : s(a,x) ∈ ({s(a,b)} : Finset (Sym2 V)) := by rw [← hTcap]; exact Finset.mem_inter.mpr ⟨by simp [finite_vertex_set_edge_encoding,Ne.symm hxa],he⟩ simp only [Finset.mem_singleton,Sym2.eq_iff] at hh aesop have hfreeBX : s(b,x) ∉ W := by intro he have hh : s(b,x) ∈ ({s(a,b)} : Finset (Sym2 V)) := by rw [← hTcap]; exact Finset.mem_inter.mpr ⟨by simp [finite_vertex_set_edge_encoding,Ne.symm hxb],he⟩ simp only [Finset.mem_singleton,Sym2.eq_iff] at hh aesop have hfreeCX : s(c,x) ∉ W := by intro he have hh : s(c,x) ∈ ({s(a,c)} : Finset (Sym2 V)) := by rw [← hUcap]; exact Finset.mem_inter.mpr ⟨by simp [finite_vertex_set_edge_encoding,Ne.symm hxc],he⟩ simp only [Finset.mem_singleton,Sym2.eq_iff] at hh aesop refine ⟨x,by simp [hxa,hxb,hxc],?_,?_⟩ · constructor · have habG : G.Adj a b := (htri _ hp).1 (by simp) (by simp) hab have hacG : G.Adj a c := (htri _ hp).1 (by simp) (by simp) hac have hbcG : G.Adj b c := (htri _ hp).1 (by simp) (by simp) hbc have haxG : G.Adj a x := hTG.1 (by simp) (by simp) (Ne.symm hxa) have hbxG : G.Adj b x := hTG.1 (by simp) (by simp) (Ne.symm hxb) have hcxG : G.Adj c x := hUG.1 (by simp) (by simp) (Ne.symm hxc) intro u hu v hv huv simp only [Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton] at hu hv rcases hu with rfl | rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl | rfl all_goals first | contradiction | assumption | exact SimpleGraph.Adj.symm (by assumption) · have heq : ({a,b,c,x} : Finset V) = insert x {a,b,c} := by ext z simp only [Finset.mem_insert,Finset.mem_singleton] tauto rw [heq,Finset.card_insert_of_notMem (by simp [hxa,hxb,hxc]), In700.in700_card_three hab hac hbc] · intro v hv simp only [Finset.mem_insert,Finset.mem_singleton] at hv rcases hv with rfl | rfl | rfl · simpa only [Sym2.eq_swap] using hfreeAX · simpa only [Sym2.eq_swap] using hfreeBX · simpa only [Sym2.eq_swap] using hfreeCXend In701namespace In701lemma k4_all_forced {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (a b c x : V) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (hp : ({a,b,c} : Finset V) ∈ P) (hx : x ∉ ({a,b,c} : Finset V)) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset V)) (hfree : ∀ v ∈ ({a,b,c} : Finset V), s(x,v) ∉ P.biUnion finite_vertex_set_edge_encoding) : finite_vertex_set_edge_encoding ({a,b,c} : Finset V) ⊆ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) := by classical have hxa : x ≠ a := by intro h; subst x; exact hx (by simp) have hxb : x ≠ b := by intro h; subst x; exact hx (by simp) have hxc : x ≠ c := by intro h; subst x; exact hx (by simp) let W := P.biUnion finite_vertex_set_edge_encoding have hPacked (e : Sym2 V) (he : e ∈ finite_vertex_set_edge_encoding ({a,b,c} : Finset V)) : e ∈ W := Finset.mem_biUnion.mpr ⟨{a,b,c},hp,he⟩ have hfa : s(a,x) ∉ W := by simpa only [Sym2.eq_swap] using hfree a (by simp) have hfb : s(b,x) ∉ W := by simpa only [Sym2.eq_swap] using hfree b (by simp) have hfc : s(c,x) ∉ W := by simpa only [Sym2.eq_swap] using hfree c (by simp) have ht (u v : V) (hu : u ∈ ({a,b,c} : Finset V)) (hv : v ∈ ({a,b,c} : Finset V)) (huv : u ≠ v) (hux : u ≠ x) (hvx : v ≠ x) : G.IsNClique 3 ({u,v,x} : Finset V) := by apply In700.in700_clique_subset G {a,b,c,x} {u,v,x} hk4 · intro z hz simp only [Finset.mem_insert,Finset.mem_singleton] at hz ⊢ simp only [Finset.mem_insert,Finset.mem_singleton] at hu hv aesop · exact In700.in700_card_three huv hux hvx have hab' := In700.in700_triangle_witness G W a b x hab (Ne.symm hxa) (Ne.symm hxb) (ht a b (by simp) (by simp) hab (Ne.symm hxa) (Ne.symm hxb)) (hPacked _ (by simp [finite_vertex_set_edge_encoding,hab])) hfb (by simpa only [Sym2.eq_swap] using hfa) have hbc' := In700.in700_triangle_witness G W b c x hbc (Ne.symm hxb) (Ne.symm hxc) (ht b c (by simp) (by simp) hbc (Ne.symm hxb) (Ne.symm hxc)) (hPacked _ (by simp [finite_vertex_set_edge_encoding,hbc])) hfc (by simpa only [Sym2.eq_swap] using hfb) have hca' := In700.in700_triangle_witness G W c a x (Ne.symm hac) (Ne.symm hxc) (Ne.symm hxa) (ht c a (by simp) (by simp) (Ne.symm hac) (Ne.symm hxc) (Ne.symm hxa)) (hPacked _ (by simp [finite_vertex_set_edge_encoding,Ne.symm hac])) hfa (by simpa only [Sym2.eq_swap] using hfc) rw [In700.in700_encoding_three a b c hab hac hbc] intro e he simp only [Finset.mem_insert,Finset.mem_singleton] at he rcases he with rfl | rfl | rfl <;> assumptionend In701open In701lemma in701_choose {V : Type*} [DecidableEq V] (a b c : V) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (F : Finset (Sym2 V)) (hmarked : 2 ≤ (finite_vertex_set_edge_encoding ({a,b,c} : Finset V) ∩ F).card) : (s(a,b) ∈ F ∧ s(a,c) ∈ F) ∨ (s(b,a) ∈ F ∧ s(b,c) ∈ F) ∨ (s(c,a) ∈ F ∧ s(c,b) ∈ F) := by have hmany : 1 < (finite_vertex_set_edge_encoding ({a,b,c} : Finset V) ∩ F).card := by omega obtain ⟨e,he,f,hf,hef⟩ := Finset.one_lt_card.mp hmany have heF : e ∈ F := (Finset.mem_inter.mp he).2 have hfF : f ∈ F := (Finset.mem_inter.mp hf).2 have heE := (Finset.mem_inter.mp he).1 have hfE := (Finset.mem_inter.mp hf).1 rw [In700.in700_encoding_three a b c hab hac hbc] at heE hfE simp only [Finset.mem_insert,Finset.mem_singleton] at heE hfE rcases heE with heE | heE | heE · subst e rcases hfE with hfE | hfE | hfE · subst f; exact (hef rfl).elim · subst f; right; left; exact ⟨by simpa only [Sym2.eq_swap] using heF,hfF⟩ · subst f; left; exact ⟨heF,by simpa only [Sym2.eq_swap] using hfF⟩ · subst e rcases hfE with hfE | hfE | hfE · subst f; right; left; exact ⟨by simpa only [Sym2.eq_swap] using hfF,heF⟩ · subst f; exact (hef rfl).elim · subst f; right; right; exact ⟨hfF, by simpa only [Sym2.eq_swap] using heF⟩ · subst e rcases hfE with hfE | hfE | hfE · subst f; left; exact ⟨hfF,by simpa only [Sym2.eq_swap] using heF⟩ · subst f; right; right; exact ⟨heF,by simpa only [Sym2.eq_swap] using hfF⟩ · subst f; exact (hef rfl).elimlemma in701_k4_choose (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (a b c : Fin n) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hchoose : let F := (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) (s(a,b) ∈ F ∧ s(a,c) ∈ F) ∨ (s(b,a) ∈ F ∧ s(b,c) ∈ F) ∨ (s(c,a) ∈ F ∧ s(c,b) ∈ F)) : ∃ x, x ∉ ({a,b,c} : Finset (Fin n)) ∧ G.IsNClique 4 ({a,b,c,x} : Finset (Fin n)) ∧ (∀ v ∈ ({a,b,c} : Finset (Fin n)), s(x,v) ∉ P.biUnion finite_vertex_set_edge_encoding) := by classical rcases hchoose with ⟨h1,h2⟩ | ⟨h1,h2⟩ | ⟨h1,h2⟩ · exact two_edges_ordered G P htri hdisj hmax a b c hab hac hbc hp h1 h2 · have hperm : ({b,a,c} : Finset (Fin n)) = {a,b,c} := by ext z; simp only [Finset.mem_insert,Finset.mem_singleton]; tauto have hperm4 (x : Fin n) : ({b,a,c,x} : Finset (Fin n)) = {a,b,c,x} := by ext z; simp only [Finset.mem_insert,Finset.mem_singleton]; tauto have hp' : ({b,a,c} : Finset (Fin n)) ∈ P := by simpa only [hperm] using hp obtain ⟨x,hx,hfour,hfree⟩ := two_edges_ordered G P htri hdisj hmax b a c (Ne.symm hab) hbc hac hp' h1 h2 exact ⟨x,by simpa only [hperm] using hx,by simpa only [hperm4] using hfour,by simpa only [hperm] using hfree⟩ · have hperm : ({c,a,b} : Finset (Fin n)) = {a,b,c} := by ext z; simp only [Finset.mem_insert,Finset.mem_singleton]; tauto have hperm4 (x : Fin n) : ({c,a,b,x} : Finset (Fin n)) = {a,b,c,x} := by ext z; simp only [Finset.mem_insert,Finset.mem_singleton]; tauto have hp' : ({c,a,b} : Finset (Fin n)) ∈ P := by simpa only [hperm] using hp obtain ⟨x,hx,hfour,hfree⟩ := two_edges_ordered G P htri hdisj hmax c a b (Ne.symm hac) (Ne.symm hbc) hab hp' h1 h2 exact ⟨x,by simpa only [hperm] using hx,by simpa only [hperm4] using hfour,by simpa only [hperm] using hfree⟩lemma in701_insert_four {V : Type*} [DecidableEq V] (a b c x : V) : insert x ({a,b,c} : Finset V) = {a,b,c,x} := by ext z simp only [Finset.mem_insert,Finset.mem_singleton] tautolemma in701_main_ordered (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (a b c : Fin n) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hmarked : 2 ≤ (finite_vertex_set_edge_encoding ({a,b,c} : Finset (Fin n)) ∩ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card) : ∃ x : Fin n, x ∉ ({a,b,c} : Finset (Fin n)) ∧ G.IsNClique 4 (insert x {a,b,c}) ∧ (∀ v ∈ ({a,b,c} : Finset (Fin n)), s(x,v) ∉ P.biUnion finite_vertex_set_edge_encoding) ∧ finite_vertex_set_edge_encoding ({a,b,c} : Finset (Fin n)) ⊆ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) := by classical let F := (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) have hmarked' : 2 ≤ (finite_vertex_set_edge_encoding ({a,b,c} : Finset (Fin n)) ∩ F).card := hmarked have hchoose := in701_choose a b c hab hac hbc F hmarked' have hK := in701_k4_choose n G P htri hdisj hmax a b c hab hac hbc hp hchoose obtain ⟨x,hx,hfour,hfree⟩ := hK refine ⟨x,hx,?_,hfree,k4_all_forced G P a b c x hab hac hbc hp hx hfour hfree⟩ rw [in701_insert_four] exact hfourtheorem simple_graph_maximum_packing_two_forced_edges_k4 (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P : Finset (Finset (Fin n))) (p : Finset (Fin n)) (htri : ∀ t ∈ P, G.IsNClique 3 t) (hdisj : (P : Set (Finset (Fin n))).Pairwise (fun t u => (t ∩ u).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : p ∈ P) (hmarked : 2 ≤ (finite_vertex_set_edge_encoding p ∩ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id)).card) : ∃ x : Fin n, x ∉ p ∧ G.IsNClique 4 (insert x p) ∧ (∀ v ∈ p, s(x,v) ∉ P.biUnion finite_vertex_set_edge_encoding) ∧ finite_vertex_set_edge_encoding p ⊆ (((simple_graph_triangle_edge_family G).filter (fun t => (t ∩ P.biUnion finite_vertex_set_edge_encoding).card = 1)).biUnion id) := by classical obtain ⟨a,b,c,hab,hac,hbc,hpEq⟩ := Finset.card_eq_three.mp (htri p hp).card_eq subst p exact in701_main_ordered n G P htri hdisj hmax a b c hab hac hbc hp hmarked