simple_graph_pair_stable_private_k4_packing_incidence
theoremverified
Let a maximum packing in a two-edge-stable graph contain abc, with a and b private to that packing triangle. If abcx is a four-clique whose x-spokes are unused by the packing, then x occurs in at least two packing triangles, c occurs in at least three, and the packing contains at least five triangles.
Statement
theorem simple_graph_pair_stable_private_k4_packing_incidence (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)) (hmax : P.card = simple_graph_triangle_packing_number G) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hprivate : ∀ q ∈ P, q ≠ ({a,b,c} : Finset (Fin n)) → a ∉ q ∧ b ∉ q) (hfree : ∀ v ∈ ({a,b,c} : Finset (Fin n)), s(x,v) ∉ P.biUnion finite_vertex_set_edge_encoding) : 2 ≤ (P.filter (fun q => x ∈ q)).card ∧ 3 ≤ (P.filter (fun q => c ∈ q)).card ∧ 5 ≤ P.card
- Source
- Private-witness exchange in the internal-anchor branch of the triangle-packing campaign; compare https://arxiv.org/abs/2001.00257, Section 3.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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).
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- simple_graph_pair_stable_vertex_link_edge_spoke_exchangeIn a two-edge-stable graph, for every edge yz of the link at x and every neighbor w of x, another link edge meets yz and avoids w.
- simple_graph_maximum_triangle_packing_edge_meetsEvery triangle shares an edge with a member of a maximum edge-disjoint triangle packing.
Lean source view module on GitHub
open scoped Sym2 set_option maxRecDepth 10000 set_option maxHeartbeats 2000000 lemma in694inc_private_swap_impossible {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (p t u : Finset V) (htri : ∀ q ∈ P, G.IsNClique 3 q) (hdisj : (P : Set (Finset V)).Pairwise (fun q r => (q ∩ r).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : p ∈ P) (ht : G.IsNClique 3 t) (hu : G.IsNClique 3 u) (htu : (t ∩ u).card ≤ 1) (htpriv : ∀ q ∈ P, q ≠ p → (t ∩ q).card ≤ 1) (hupriv : ∀ q ∈ P, q ≠ p → (u ∩ q).card ≤ 1) : False := by classical let R := P.erase p have hRt : t ∉ R := by intro htR have htP := Finset.mem_of_mem_erase htR have htp := (Finset.ne_of_mem_erase htR) have h := htpriv t htP htp rw [Finset.inter_self, ht.card_eq] at h omega have hRu : u ∉ R := by intro huR have huP := Finset.mem_of_mem_erase huR have hup := (Finset.ne_of_mem_erase huR) have h := hupriv u huP hup rw [Finset.inter_self, hu.card_eq] at h omega have htu' : t ≠ u := by intro h; subst u rw [Finset.inter_self, ht.card_eq] at htu omega let Q := insert t (insert u R) have hQcl : ∀ q ∈ Q, G.IsNClique 3 q := by intro q hq simp only [Q, Finset.mem_insert] at hq rcases hq with rfl | rfl | hq · exact ht · exact hu · exact htri q (Finset.mem_of_mem_erase hq) have hQpair : (Q : Set (Finset V)).Pairwise (fun q r => (q ∩ r).card ≤ 1) := by have hRpair : (R : Set (Finset V)).Pairwise (fun q r => (q ∩ r).card ≤ 1) := by intro q hq r hr hne exact hdisj (Finset.mem_of_mem_erase hq) (Finset.mem_of_mem_erase hr) hne change ((insert t (insert u R) : Finset (Finset V)) : Set (Finset V)).Pairwise _ rw [Finset.coe_insert, Finset.coe_insert] apply Set.Pairwise.insert · apply Set.Pairwise.insert hRpair intro q hq _ have h := hupriv q (Finset.mem_of_mem_erase hq) (Finset.ne_of_mem_erase hq) exact ⟨h, by rw [Finset.inter_comm]; exact h⟩ · intro q hq _ rcases Set.mem_insert_iff.mp hq with rfl | hq · exact ⟨htu, by rw [Finset.inter_comm]; exact htu⟩ · have h := htpriv q (Finset.mem_of_mem_erase hq) (Finset.ne_of_mem_erase hq) exact ⟨h, by rw [Finset.inter_comm]; exact h⟩ have hQcard : Q.card = P.card + 1 := by have ht' : t ∉ insert u R := by simp [htu', hRt] have hp_pos : 0 < P.card := Finset.card_pos.mpr ⟨p, hp⟩ rw [show Q = insert t (insert u (P.erase p)) by rfl, Finset.card_insert_of_notMem ht', Finset.card_insert_of_notMem hRu, Finset.card_erase_of_mem hp] omega have hbdd : BddAbove {n | ∃ T : Finset (Finset V), (∀ a ∈ T, G.IsNClique 3 a) ∧ (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} := by refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩ rintro n ⟨T, -, -, rfl⟩ exact Finset.card_le_univ T have hle : Q.card ≤ simple_graph_triangle_packing_number G := by unfold simple_graph_triangle_packing_number exact le_csSup hbdd ⟨Q, hQcl, hQpair, rfl⟩ omega lemma in694inc_private_pair_card_le_one {V : Type*} [DecidableEq V] (q : Finset V) (a b y : V) (ha : a ∉ q) (hb : b ∉ q) : (({a,b,y} : Finset V) ∩ q).card ≤ 1 := by apply Finset.card_le_one.mpr intro v hv w hw simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hv hw aesop lemma in694inc_private_free_pair_card_le_one {V : Type*} [DecidableEq V] (q : Finset V) (a c x : V) (ha : a ∉ q) (hcx : ¬ (c ∈ q ∧ x ∈ q)) : (({a,c,x} : Finset V) ∩ q).card ≤ 1 := by apply Finset.card_le_one.mpr intro v hv w hw simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hv hw aesop lemma in694inc_private_k4_codegree {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (a b c x : V) (htri : ∀ q ∈ P, G.IsNClique 3 q) (hdisj : (P : Set (Finset V)).Pairwise (fun q r => (q ∩ r).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : ({a,b,c} : Finset V) ∈ P) (hab : G.Adj a b) (hac : G.Adj a c) (hax : G.Adj a x) (hcx : G.Adj c x) (hbc : b ≠ c) (hbx : b ≠ x) (hprivate : ∀ q ∈ P, q ≠ ({a,b,c} : Finset V) → a ∉ q ∧ b ∉ q) (hfreecx : ∀ q ∈ P, ¬ (c ∈ q ∧ x ∈ q)) : ∀ y, G.Adj a y → G.Adj b y → y = c ∨ y = x := by intro y hay hby by_contra hn push_neg at hn have hyc : y ≠ c := hn.1 have hyx : y ≠ x := hn.2 have hab' := hab.ne have hac' := hac.ne have hax' := hax.ne have hcx' := hcx.ne have hay' := hay.ne have hby' := hby.ne have ht : G.IsNClique 3 ({a,b,y} : Finset V) := by constructor · intro v hv w hw hvw simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hv hw rcases hv with rfl | rfl | rfl <;> rcases hw with rfl | rfl | rfl <;> aesop (add safe [hab.symm, hay.symm, hby.symm]) · simp [hab', hay', hby', Ne.symm hab', Ne.symm hay', Ne.symm hby'] have hu : G.IsNClique 3 ({a,c,x} : Finset V) := by constructor · intro v hv w hw hvw simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hv hw rcases hv with rfl | rfl | rfl <;> rcases hw with rfl | rfl | rfl <;> aesop (add safe [hac.symm, hax.symm, hcx.symm]) · simp [hac', hax', hcx', Ne.symm hac', Ne.symm hax', Ne.symm hcx'] have htu : (({a,b,y} : Finset V) ∩ {a,c,x}).card ≤ 1 := by apply Finset.card_le_one.mpr intro v hv w hw simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hv hw aesop apply in694inc_private_swap_impossible G P {a,b,c} {a,b,y} {a,c,x} htri hdisj hmax hp ht hu htu · intro q hq hqp obtain ⟨ha,hb⟩ := hprivate q hq hqp exact in694inc_private_pair_card_le_one q a b y ha hb · intro q hq hqp obtain ⟨ha,hb⟩ := hprivate q hq hqp exact in694inc_private_free_pair_card_le_one q a c x ha (hfreecx q hq) lemma in694inc_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 simp only [Finset.card_insert_eq_ite, Finset.mem_insert, Finset.mem_singleton, Finset.card_singleton] at h split_ifs at h <;> simp_all lemma in694inc_private_k4_edge_codegree_two (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)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hprivate : ∀ q ∈ P, q ≠ ({a,b,c} : Finset (Fin n)) → a ∉ q ∧ b ∉ q) (hfree : ∀ v ∈ ({a,b,c} : Finset (Fin n)), s(x,v) ∉ P.biUnion finite_vertex_set_edge_encoding) : ∀ y : Fin n, G.Adj a y → G.Adj b y → y = c ∨ y = x := by classical obtain ⟨hab,hac,hax,hbc,hbx,hcx⟩ := in694inc_four_distinct a b c x hk4.card_eq have ha : a ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hb : b ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hc : c ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hx : x ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hadj := hk4.isClique have hfreecx : ∀ q ∈ P, ¬ (c ∈ q ∧ x ∈ q) := by intro q hq ⟨hcq,hxq⟩ have hmem : s(x,c) ∈ finite_vertex_set_edge_encoding q := by simp [finite_vertex_set_edge_encoding, Sym2.mk_isDiag_iff, hxq, hcq, Ne.symm hcx] apply hfree c (by simp) exact Finset.mem_biUnion.mpr ⟨q,hq,hmem⟩ exact in694inc_private_k4_codegree G P a b c x htri hdisj hmax hp (hadj ha hb hab) (hadj ha hc hac) (hadj ha hx hax) (hadj hc hx hcx) hbc hbx hprivate hfreecx lemma in694inc_link_anchor_neighbor (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (a b c x : Fin n) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (hab : G.Adj a b) (hac : G.Adj a c) (hax : G.Adj a x) (hbx : G.Adj b x) (hcodeg : ∀ y, G.Adj a y → G.Adj b y → y = c ∨ y = x) : ∃ y, y ≠ a ∧ y ≠ b ∧ y ≠ c ∧ y ≠ x ∧ G.Adj a y ∧ G.Adj x y := by classical obtain ⟨u,v, hau,hav,huv,hm,huc,hvc,hne⟩ := simple_graph_pair_stable_vertex_link_edge_spoke_exchange n G a hstable b x c hab hax hbx hac have hub : u ≠ b := by intro h; subst u rcases hcodeg v hav huv with hvc' | hvx · exact hvc hvc' · subst v; exact hne rfl have hvb : v ≠ b := by intro h; subst v rcases hcodeg u hau huv.symm with huc' | hux · exact huc huc' · subst u; apply hne; exact Sym2.eq_swap rcases hm with h | h | h | h · exact (hub h).elim · subst u exact ⟨v,hav.ne.symm,hvb,hvc,huv.ne.symm,hav,huv⟩ · exact (hvb h).elim · subst v exact ⟨u,hau.ne.symm,hub,huc,huv.ne,hau,huv.symm⟩ lemma in694inc_two_members_of_large_intersection {V : Type*} [DecidableEq V] (q : Finset V) (a x y : V) (ha : a ∉ q) (h : 2 ≤ (q ∩ ({a,x,y} : Finset V)).card) : x ∈ q ∧ y ∈ q := by by_contra hn have hle : (q ∩ ({a,x,y} : Finset V)).card ≤ 1 := by apply Finset.card_le_one.mpr intro v hv w hw simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hv hw aesop omega lemma in694inc_anchor_triangle_meets_other_packing {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (p : Finset V) (a x y : V) (htri : ∀ q ∈ P, G.IsNClique 3 q) (hdisj : (P : Set (Finset V)).Pairwise (fun q r => (q ∩ r).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : p ∈ P) (hx : x ∉ p) (hy : y ∉ p) (hprivate : ∀ q ∈ P, q ≠ p → a ∉ q) (ht : G.IsNClique 3 ({a,x,y} : Finset V)) : ∃ q ∈ P, q ≠ p ∧ x ∈ q ∧ y ∈ q := by obtain ⟨q,hq,hmeet⟩ := simple_graph_maximum_triangle_packing_edge_meets G P htri hdisj hmax {a,x,y} ht have hqp : q ≠ p := by intro h; subst q have hle : (p ∩ ({a,x,y} : Finset V)).card ≤ 1 := by apply Finset.card_le_one.mpr intro v hv w hw simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hv hw aesop omega obtain ⟨hqx,hqy⟩ := in694inc_two_members_of_large_intersection q a x y (hprivate q hq hqp) hmeet exact ⟨q,hq,hqp,hqx,hqy⟩ lemma in694inc_distinct_packed_triangles_no_shared_pair {V : Type*} [DecidableEq V] (P : Finset (Finset V)) (q r : Finset V) (x y : V) (hdisj : (P : Set (Finset V)).Pairwise (fun q r => (q ∩ r).card ≤ 1)) (hq : q ∈ P) (hr : r ∈ P) (hqr : q ≠ r) (hqx : x ∈ q) (hqy : y ∈ q) (hxy : x ≠ y) : ¬ (x ∈ r ∧ y ∈ r) := by intro ⟨hrx,hry⟩ have hs : ({x,y} : Finset V) ⊆ q ∩ r := by intro v hv simp only [Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with rfl | rfl <;> simp_all have hcard := Finset.card_le_card hs have hpair := hdisj hq hr hqr simp [hxy] at hcard omega lemma in694inc_mixed_anchor_witnesses_impossible {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P : Finset (Finset V)) (p q : Finset V) (a b x y z : V) (htri : ∀ r ∈ P, G.IsNClique 3 r) (hdisj : (P : Set (Finset V)).Pairwise (fun r s => (r ∩ s).card ≤ 1)) (hmax : P.card = simple_graph_triangle_packing_number G) (hp : p ∈ P) (hq : q ∈ P) (hqp : q ≠ p) (ha : a ∈ p) (hb : b ∈ p) (hab : a ≠ b) (hx : x ∉ p) (hy : y ∉ p) (hz : z ∉ p) (hyz : y ≠ z) (hqx : x ∈ q) (hqy : y ∈ q) (hqz : z ∈ q) (hxy : x ≠ y) (hxz : x ≠ z) (hprivate : ∀ r ∈ P, r ≠ p → a ∉ r ∧ b ∉ r) (ht : G.IsNClique 3 ({a,x,y} : Finset V)) (hu : G.IsNClique 3 ({b,x,z} : Finset V)) : False := by have htu : (({a,x,y} : Finset V) ∩ {b,x,z}).card ≤ 1 := by apply Finset.card_le_one.mpr intro v hv w hw simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hv hw aesop apply in694inc_private_swap_impossible G P q {a,x,y} {b,x,z} htri hdisj hmax hq ht hu htu · intro r hr hrq by_cases hrp : r = p · subst r apply Finset.card_le_one.mpr intro v hv w hw simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hv hw aesop · obtain ⟨har,hbr⟩ := hprivate r hr hrp have hxy' := in694inc_distinct_packed_triangles_no_shared_pair P q r x y hdisj hq hr (Ne.symm hrq) hqx hqy hxy exact in694inc_private_free_pair_card_le_one r a x y har hxy' · intro r hr hrq by_cases hrp : r = p · subst r apply Finset.card_le_one.mpr intro v hv w hw simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hv hw aesop · obtain ⟨har,hbr⟩ := hprivate r hr hrp have hxz' := in694inc_distinct_packed_triangles_no_shared_pair P q r x z hdisj hq hr (Ne.symm hrq) hqx hqz hxz exact in694inc_private_free_pair_card_le_one r b x z hbr hxz' lemma in694inc_triangle_of_edges {V : Type*} [DecidableEq V] (G : SimpleGraph V) (a b c : V) (hab : G.Adj a b) (hac : G.Adj a c) (hbc : G.Adj b c) : G.IsNClique 3 ({a,b,c} : Finset V) := by constructor · intro v hv w hw hvw simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hv hw rcases hv with rfl | rfl | rfl <;> rcases hw with rfl | rfl | rfl <;> aesop (add safe [hab.symm, hac.symm, hbc.symm]) · simp [hab.ne,hac.ne,hbc.ne] lemma in694inc_pair_stable_private_k4_anchor_incidence (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)) (hmax : P.card = simple_graph_triangle_packing_number G) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hprivate : ∀ q ∈ P, q ≠ ({a,b,c} : Finset (Fin n)) → a ∉ q ∧ b ∉ q) (hfree : ∀ v ∈ ({a,b,c} : Finset (Fin n)), s(x,v) ∉ P.biUnion finite_vertex_set_edge_encoding) : 2 ≤ (P.filter (fun q => x ∈ q)).card := by classical obtain ⟨hab,hac,hax,hbc,hbx,hcx⟩ := in694inc_four_distinct a b c x hk4.card_eq have ha : a ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hb : b ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hc : c ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hx : x ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hadj := hk4.isClique have hab' := hadj ha hb hab have hac' := hadj ha hc hac have hax' := hadj ha hx hax have hbc' := hadj hb hc hbc have hbx' := hadj hb hx hbx have hcodeg := in694inc_private_k4_edge_codegree_two n G P a b c x htri hdisj hmax hp hk4 hprivate hfree obtain ⟨y,hya,hyb,hyc,hyx,hay,hxy⟩ := in694inc_link_anchor_neighbor n G a b c x hstable hab' hac' hax' hbx' hcodeg have hcodeg' : ∀ v, G.Adj b v → G.Adj a v → v = c ∨ v = x := by intro v hbv hav exact hcodeg v hav hbv obtain ⟨z,hzb,hza,hzc,hzx,hbz,hxz⟩ := in694inc_link_anchor_neighbor n G b a c x hstable hab'.symm hbc' hbx' hax' hcodeg' have hyz : y ≠ z := by intro h; subst z rcases hcodeg y hay hbz with h | h · exact hyc h · exact hyx h have hxp : x ∉ ({a,b,c} : Finset (Fin n)) := by simp [Ne.symm hax, Ne.symm hbx, Ne.symm hcx] have hyp : y ∉ ({a,b,c} : Finset (Fin n)) := by simp [hya,hyb,hyc] have hzp : z ∉ ({a,b,c} : Finset (Fin n)) := by simp [hza,hzb,hzc] have ht := in694inc_triangle_of_edges G a x y hax' hay hxy have hu := in694inc_triangle_of_edges G b x z hbx' hbz hxz obtain ⟨q,hq,hqp,hqx,hqy⟩ := in694inc_anchor_triangle_meets_other_packing G P {a,b,c} a x y htri hdisj hmax hp hxp hyp (fun r hr hrp => (hprivate r hr hrp).1) ht obtain ⟨r,hr,hrp,hrx,hrz⟩ := in694inc_anchor_triangle_meets_other_packing G P {a,b,c} b x z htri hdisj hmax hp hxp hzp (fun r hr hrp => (hprivate r hr hrp).2) hu have hqr : q ≠ r := by intro h; subst r exact in694inc_mixed_anchor_witnesses_impossible G P {a,b,c} q a b x y z htri hdisj hmax hp hq hqp (by simp) (by simp) hab hxp hyp hzp hyz hqx hqy hrz (Ne.symm hyx) (Ne.symm hzx) hprivate ht hu have hs : ({q,r} : Finset (Finset (Fin n))) ⊆ P.filter (fun t => x ∈ t) := by intro t ht' simp only [Finset.mem_insert, Finset.mem_singleton] at ht' rcases ht' with rfl | rfl <;> simp_all have hcard := Finset.card_le_card hs simpa [hqr] using hcard theorem simple_graph_pair_stable_private_k4_packing_incidence (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)) (hmax : P.card = simple_graph_triangle_packing_number G) (hstable : ∀ e f : Sym2 (Fin n), e ∈ G.edgeSet → f ∈ G.edgeSet → e ≠ f → simple_graph_triangle_packing_number (G.deleteEdges {e,f}) = simple_graph_triangle_packing_number G) (hp : ({a,b,c} : Finset (Fin n)) ∈ P) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hprivate : ∀ q ∈ P, q ≠ ({a,b,c} : Finset (Fin n)) → a ∉ q ∧ b ∉ q) (hfree : ∀ v ∈ ({a,b,c} : Finset (Fin n)), s(x,v) ∉ P.biUnion finite_vertex_set_edge_encoding) : 2 ≤ (P.filter (fun q => x ∈ q)).card ∧ 3 ≤ (P.filter (fun q => c ∈ q)).card ∧ 5 ≤ P.card := by classical obtain ⟨hab,hac,hax,hbc,hbx,hcx⟩ := in694inc_four_distinct a b c x hk4.card_eq have ha : a ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hb : b ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hc : c ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hx : x ∈ ({a,b,c,x} : Finset (Fin n)) := by simp have hadj := hk4.isClique have ht := in694inc_triangle_of_edges G a b x (hadj ha hb hab) (hadj ha hx hax) (hadj hb hx hbx) have hcx_free : ∀ q ∈ P, ¬ (c ∈ q ∧ x ∈ q) := by intro q hq ⟨hcq,hxq⟩ have hm : s(x,c) ∈ finite_vertex_set_edge_encoding q := by simp [finite_vertex_set_edge_encoding, Sym2.mk_isDiag_iff, hxq, hcq, Ne.symm hcx] exact hfree c (by simp) (Finset.mem_biUnion.mpr ⟨q,hq,hm⟩) let p : Finset (Fin n) := {a,b,c} let t : Finset (Fin n) := {a,b,x} let R := P.erase p let Q := insert t R have hRt : t ∉ R := by intro hm have hqP := Finset.mem_of_mem_erase hm have hqp := Finset.ne_of_mem_erase hm have hn := (hprivate t hqP hqp).1 exact hn (by simp [t]) have hQcl : ∀ q ∈ Q, G.IsNClique 3 q := by intro q hq rcases Finset.mem_insert.mp hq with rfl | hq · exact ht · exact htri q (Finset.mem_of_mem_erase hq) have hQpair : (Q : Set (Finset (Fin n))).Pairwise (fun q r => (q ∩ r).card ≤ 1) := by have hRpair : (R : Set (Finset (Fin n))).Pairwise (fun q r => (q ∩ r).card ≤ 1) := by intro q hq r hr hne exact hdisj (Finset.mem_of_mem_erase hq) (Finset.mem_of_mem_erase hr) hne change ((insert t R : Finset (Finset (Fin n))) : Set (Finset (Fin n))).Pairwise _ rw [Finset.coe_insert] apply Set.Pairwise.insert hRpair intro q hq _ obtain ⟨haq,hbq⟩ := hprivate q (Finset.mem_of_mem_erase hq) (Finset.ne_of_mem_erase hq) have h := in694inc_private_pair_card_le_one q a b x haq hbq exact ⟨h, by rw [Finset.inter_comm]; exact h⟩ have hQcard : Q.card = P.card := by have hpos : 0 < P.card := Finset.card_pos.mpr ⟨p,hp⟩ rw [show Q = insert t (P.erase p) by rfl, Finset.card_insert_of_notMem hRt, Finset.card_erase_of_mem hp] omega have hQmax : Q.card = simple_graph_triangle_packing_number G := hQcard.trans hmax have htQ : t ∈ Q := by simp [Q] have hcnot_t : c ∉ t := by simp [t, Ne.symm hac, Ne.symm hbc, hcx] have hQprivate : ∀ q ∈ Q, q ≠ t → a ∉ q ∧ b ∉ q := by intro q hq hqt have hqR : q ∈ R := (Finset.mem_insert.mp hq).resolve_left hqt exact hprivate q (Finset.mem_of_mem_erase hqR) (Finset.ne_of_mem_erase hqR) have hQfree : ∀ v ∈ t, s(c,v) ∉ Q.biUnion finite_vertex_set_edge_encoding := by intro v hv hm obtain ⟨q,hq,henc⟩ := Finset.mem_biUnion.mp hm have hmem : c ∈ q ∧ v ∈ q := by have hv : (c ∈ q ∧ v ∈ q) ∧ c ≠ v := by simpa [finite_vertex_set_edge_encoding, Sym2.mk_isDiag_iff] using henc exact hv.1 rcases Finset.mem_insert.mp hq with rfl | hqR · exact hcnot_t hmem.1 · have hqP := Finset.mem_of_mem_erase hqR have hqp := Finset.ne_of_mem_erase hqR obtain ⟨haq,hbq⟩ := hprivate q hqP hqp simp only [t, Finset.mem_insert, Finset.mem_singleton] at hv rcases hv with rfl | rfl | rfl · exact haq hmem.2 · exact hbq hmem.2 · exact hcx_free q hqP hmem have hk4' : G.IsNClique 4 ({a,b,x,c} : Finset (Fin n)) := by have heq : ({a,b,x,c} : Finset (Fin n)) = {a,b,c,x} := by ext v; simp; aesop rwa [heq] have hx_bound : 2 ≤ (P.filter (fun q => x ∈ q)).card := in694inc_pair_stable_private_k4_anchor_incidence n G P a b c x htri hdisj hmax hstable hp hk4 hprivate hfree have hc_Qbound : 2 ≤ (Q.filter (fun q => c ∈ q)).card := in694inc_pair_stable_private_k4_anchor_incidence n G Q a b x c hQcl hQpair hQmax hstable htQ hk4' hQprivate hQfree let B := P.filter (fun q => c ∈ q) have hpB : p ∈ B := by simp [B,p,hp] have hsub : Q.filter (fun q => c ∈ q) ⊆ B.erase p := by intro q hq obtain ⟨hqQ,hqc⟩ := Finset.mem_filter.mp hq have hqR : q ∈ R := (Finset.mem_insert.mp hqQ).resolve_left (by intro h; subst q; exact hcnot_t hqc) exact Finset.mem_erase.mpr ⟨Finset.ne_of_mem_erase hqR, Finset.mem_filter.mpr ⟨Finset.mem_of_mem_erase hqR,hqc⟩⟩ have hBbound : 3 ≤ B.card := by have hh := Finset.card_le_card hsub rw [Finset.card_erase_of_mem hpB] at hh have hpos : 0 < B.card := Finset.card_pos.mpr ⟨p,hpB⟩ omega have hD : Disjoint B (P.filter (fun q => x ∈ q)) := by apply Finset.disjoint_left.mpr intro q hq hqx have ⟨hqP,hqc⟩ := Finset.mem_filter.mp hq have hqx' := (Finset.mem_filter.mp hqx).2 exact hcx_free q hqP ⟨hqc,hqx'⟩ have hUnion : B ∪ (P.filter (fun q => x ∈ q)) ⊆ P := by intro q hq simp only [Finset.mem_union, B, Finset.mem_filter] at hq aesop have hcard := Finset.card_le_card hUnion rw [Finset.card_union_of_disjoint hD] at hcard exact ⟨hx_bound, hBbound, by omega⟩