simple_graph_k4_attachment_of_two_triangle_edge_covers
Let two families P and Q meet every triangle of a graph in an edge, with all members of Q triangles. In a four-clique abcx, suppose no member of P contains ax or bx and no member of Q contains ab or cx. Then a member of P contains a vertex y outside abcx and either contains a or b with xy present, or contains x with ay or by present. Neither family needs to be a packing.
Statement
theorem simple_graph_k4_attachment_of_two_triangle_edge_covers (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P Q : Finset (Finset (Fin n))) (a b c x : Fin n) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hPcover : ∀ s : Finset (Fin n), G.IsNClique 3 s → ∃ t ∈ P, 2 ≤ (t ∩ s).card) (hQcover : ∀ s : Finset (Fin n), G.IsNClique 3 s → ∃ t ∈ Q, 2 ≤ (t ∩ s).card) (hQtri : ∀ t ∈ Q, G.IsNClique 3 t) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (havoid : ∀ t ∈ Q, ¬ (a ∈ t ∧ b ∈ t) ∧ ¬ (c ∈ t ∧ x ∈ t)) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset (Fin n)) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y)))- Source
- Elementary core of the pair-stable forced-K4 attachment reduction for simple_graph_triangle_cover_number_le_two_mul_packing_number.
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- simple_graph_opposite_pair_stable_k4_attachmentLet P be a maximum edge-disjoint triangle packing containing abc, and let x complete abc to a four-clique. Suppose neither ax nor bx is an…
The proof, explained
The theorem is proved by analyzing how the two triangle edge covers P and Q interact with the 4-clique abcx. Since Q covers an edge of the triangle abx but avoids ab, it contains a triangle q containing x and a vertex v ∈ {a, b}, along with a third vertex y. The avoidance conditions on Q force y to lie strictly outside {a, b, c, x}, showing q = {v, x, y} with edges xy and vy present. Because P covers an edge of q but cannot contain the spoke vx, P must contain a member t containing y and either v or x, which is distinct from {a, b, c} and establishes the attachment configuration.
Any set intersecting {a, b, x} in at least two elements contains at least one of the pairs {a, b}, {a, x}, or {b, x}.
We proceed by contradiction (by_contra hn). If none of the three pairs were contained in s, then no two distinct elements of {a, b, x} could both belong to s. Hence any two elements in s ∩ {a, b, x} would be equal (Finset.card_le_one.mpr), which forces the cardinality of the intersection to be at most 1 (hle). This contradicts the hypothesis that the intersection has at least 2 elements, and linear arithmetic closes the contradiction (omega).
uses
Finset.card_le_one.mprclassical by_contra hn have hle : (s ∩ {a,b,x}).card ≤ 1 := by apply Finset.card_le_one.mpr intro u hu v hv simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hu hv aesop omega
A three-element set s containing a and x contains an element y distinct from both a and x.
Suppose for contradiction that no such y exists (by_contra hn). Then every element of s must be equal to a or x, meaning s ⊆ {a, x} (hsub). By monotonicity of cardinality (Finset.card_le_card), |s| ≤ |{a, x}|. Because any two-element set has cardinality at most 2 (Finset.card_le_two), |s| ≤ 2, contradicting |s| = 3 via linear arithmetic (omega).
uses
Finset.card_le_card,Finset.card_le_twoclassical by_contra hn have hsub : s ⊆ {a,x} := by intro y hy simp only [not_exists, not_and] at hn simp only [Finset.mem_insert, Finset.mem_singleton] by_contra hn2 exact hn y hy (by aesop) (by aesop) have hc := Finset.card_le_card hsub have htwo := Finset.card_le_two (a := a) (b := x) omega
There exists a triangle q in Q containing x and a vertex v ∈ {a, b} with v ≠ x.
Applying the edge-cover hypothesis hQcover to the triangle {a, b, x} yields a member q ∈ Q intersecting {a, b, x} in at least two vertices. Since q ∈ Q, it is a triangle clique (hqcl). By two_of_inter_three, q must contain {a, b}, {a, x}, or {b, x}. Because Q avoids the edge ab (havoid), containing {a, b} is impossible (False.elim). Thus q contains x and some vertex v ∈ {a, b}. Since a ≠ x and b ≠ x, we also have v ≠ x (hvx).
uses
two_of_inter_three,False.elimclassical obtain ⟨q, hqQ, hmeet⟩ := hQcover {a,b,x} habx have hqcl := hQtri q hqQ have hqa := havoid q hqQ have hv : ∃ v : V, (v = a ∨ v = b) ∧ v ∈ q ∧ x ∈ q := by rcases two_of_inter_three q a b x hmeet with hab | hax | hbx · exact False.elim (hqa.1 hab) · exact ⟨a, Or.inl rfl, hax.1, hax.2⟩ · exact ⟨b, Or.inr rfl, hbx.1, hbx.2⟩ obtain ⟨v, hvab, hvq, hxq⟩ := hv have hvx : v ≠ x := by rcases hvab with rfl | rfl <;> assumption
The third vertex y of q lies outside {a, b, c, x}, so q = {v, x, y}, and the edges xy and vy are present in G.
Since q has 3 vertices and contains distinct vertices v and x, third_vertex_of_three produces a third vertex y ∈ q distinct from both. We verify that y ∉ {a, b, c, x} (hyoutside): y ≠ v and y ≠ x by construction; if y were the other vertex in {a, b}, then q would contain both a and b, violating havoid; if y = c, then q would contain both c and x, again violating havoid. Since {v, x, y} ⊆ q and both have 3 vertices, they are equal (Finset.eq_of_subset_of_card_le). As q is a clique, xy and vy are edges of G (using Ne.symm).
uses
third_vertex_of_three,Finset.eq_of_subset_of_card_le,Ne.symmobtain ⟨y, hyq, hyv, hyx⟩ := third_vertex_of_three q v x hqcl.card_eq hvq hxq have hyoutside : y ∉ ({a,b,c,x} : Finset V) := by simp only [Finset.mem_insert, Finset.mem_singleton, not_or] rcases hvab with rfl | rfl <;> aesop have hqeq : ({v,x,y} : Finset V) = q := by apply Finset.eq_of_subset_of_card_le · simp [Finset.insert_subset, hvq, hxq, hyq] · have hcard : ({v,x,y} : Finset V).card = 3 := by simp [hvx, hyv, hyx, Ne.symm hvx, Ne.symm hyv, Ne.symm hyx] have hcq := hqcl.card_eq omega have hxy : G.Adj x y := hqcl.isClique hxq hyq (Ne.symm hyx) have hvy : G.Adj v y := hqcl.isClique hvq hyq (Ne.symm hyv)
The family P contains a member t containing y and at least one of v or x.
Applying the cover hypothesis hPcover to the triangle q = {v, x, y} yields a member t ∈ P meeting {v, x, y} in at least two vertices (htp). By two_of_inter_three, t contains at least one of the pairs {v, x}, {v, y}, or {x, y}. However, t cannot contain {v, x} (hnotvx), because v ∈ {a, b} and hspokes forbids any member of P from containing ax or bx; this contradiction is eliminated (False.elim). In the remaining cases, t contains either {v, y} or {x, y}, so in particular y ∈ t (hyt).
uses
two_of_inter_three,False.elimobtain ⟨t, htP, htp⟩ := hPcover q hqcl rw [← hqeq] at htp have hnotvx : ¬ (v ∈ t ∧ x ∈ t) := by rcases hvab with rfl | rfl · intro h; exact (hspokes t htP).1 ⟨h.2, h.1⟩ · intro h; exact (hspokes t htP).2 ⟨h.2, h.1⟩ have hyt : y ∈ t := by rcases two_of_inter_three t v x y htp with hvx' | hvy' | hxy' · exact False.elim (hnotvx hvx') · exact hvy'.2 · exact hxy'.2
The set t is not equal to {a, b, c}.
If t were equal to {a, b, c}, then because y ∈ t, y would belong to {a, b, c}. This contradicts the earlier fact that y ∉ {a, b, c, x} (hyoutside).
have htne : t ≠ ({a,b,c} : Finset V) := by intro h apply hyoutside rw [h] at hyt simp only [Finset.mem_insert, Finset.mem_singleton] at hyt ⊢ aesop
The member t and vertex y satisfy the core attachment conclusion.
We inspect which pair of {v, x, y} is contained in t using two_of_inter_three. The case {v, x} ⊆ t is eliminated as before (False.elim). If {v, y} ⊆ t, then since v ∈ {a, b} and xy is an edge, t contains a or b with xy present (Or.inl). If {x, y} ⊆ t, then x ∈ t, and since vy is an edge with v ∈ {a, b}, either ay or by is an edge (Or.inr). Together with t ≠ {a, b, c} and y ∉ {a, b, c, x}, this proves the core existential claim.
uses
two_of_inter_three,False.elim,Or.inl,Or.inrrcases two_of_inter_three t v x y htp with hvx' | hvy' | hxy' · exact False.elim (hnotvx hvx') · refine ⟨t, htP, htne, y, hvy'.2, hyoutside, Or.inl ⟨?_, hxy⟩⟩ rcases hvab with rfl | rfl <;> aesop · refine ⟨t, htP, htne, y, hxy'.2, hyoutside, Or.inr ⟨hxy'.1, ?_⟩⟩ rcases hvab with rfl | rfl <;> aesop
The vertices a, b, and x of the 4-clique {a, b, c, x} are pairwise distinct.
If a = x, then {a, b, c, x} collapses to {a, b, c}, which has cardinality at most 3 (Finset.card_le_three). By monotonicity (Finset.card_le_card), the 4-clique would have size at most 3, contradicting |{a, b, c, x}| = 4 (hk4.card_eq); linear arithmetic derives a contradiction (omega), so a ≠ x. Symmetrical arguments establish b ≠ x and a ≠ b.
uses
Finset.card_le_card,Finset.card_le_threeclassical have hax : a ≠ x := by intro h; subst x have hsub : ({a,b,c,a} : Finset V) ⊆ {a,b,c} := by intro z hz; simp only [Finset.mem_insert, Finset.mem_singleton] at hz ⊢; aesop have hc := Finset.card_le_card hsub have h3 := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega have hbx : b ≠ x := by intro h; subst x have hsub : ({a,b,c,b} : Finset V) ⊆ {a,b,c} := by intro z hz; simp only [Finset.mem_insert, Finset.mem_singleton] at hz ⊢; aesop have hc := Finset.card_le_card hsub have h3 := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega have hab : a ≠ b := by intro h; subst b have hsub : ({a,a,c,x} : Finset V) ⊆ {a,c,x} := by simp have hc := Finset.card_le_card hsub have h3 := Finset.card_le_three (a := a) (b := c) (c := x) have h4 := hk4.card_eq omega
The subset {a, b, x} is a 3-clique, and the attachment theorem holds for any finite vertex type.
Because {a, b, x} is a subset of the 4-clique, it is a clique by SimpleGraph.IsClique.subset. Since a, b, x were shown to be pairwise distinct (using Ne.symm), {a, b, x} has size 3. Applying two_covers_k4_attachment_core directly yields the result for general finite types.
uses
SimpleGraph.IsClique.subset,Ne.symm,two_covers_k4_attachment_corehave habx : G.IsNClique 3 ({a,b,x} : Finset V) := by refine ⟨SimpleGraph.IsClique.subset ?_ hk4.isClique, ?_⟩ · intro z hz simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hz ⊢ aesop · simp [hab, hax, hbx, Ne.symm hab, Ne.symm hax, Ne.symm hbx] exact two_covers_k4_attachment_core G P Q a b c x hax hbx habx hPcover hQcover hQtri hspokes havoid
The main theorem holds for graphs on vertices Fin n.
The main theorem simple_graph_k4_attachment_of_two_triangle_edge_covers is an immediate specialization of two_covers_k4_attachment to V = Fin n.
uses
two_covers_k4_attachmentexact two_covers_k4_attachment G P Q a b c x hk4 hPcover hQcover hQtri hspokes havoid
Finset.card_le_one.mpr- If every pair of elements in a finite set are equal, then the set has cardinality at most 1.
Finset.card_le_card- If a finite set s is a subset of t, then the cardinality of s is at most that of t.
Finset.card_le_two- A set of the form {a, b} has cardinality at most 2.
Finset.card_le_three- A set of the form {a, b, c} has cardinality at most 3.
two_of_inter_three- If a finite set intersects {a, b, x} in at least 2 elements, it contains at least one of the pairs {a, b}, {a, x}, or {b, x}.
third_vertex_of_three- A 3-element set containing a and x contains a third element distinct from both a and x.
Finset.eq_of_subset_of_card_le- If s is a subset of t and the cardinality of t is at most that of s, then s = t.
Ne.symm- Symmetry of inequality: if a ≠ b, then b ≠ a.
False.elim- From a contradiction (falsehood), any proposition can be derived (ex falso quodlibet).
Or.inl- Infers a disjunction A ∨ B from a proof of the left disjunct A.
Or.inr- Infers a disjunction A ∨ B from a proof of the right disjunct B.
SimpleGraph.IsClique.subset- Any subset of a clique in a simple graph is also a clique.
two_covers_k4_attachment_core- Under the triangle edge cover and edge avoidance hypotheses, a 4-clique with a triangle abx contains an attachment triangle in P meeting the outside vertex conditions.
two_covers_k4_attachment- The attachment theorem on an arbitrary finite vertex type, establishing distinctness of vertices from the 4-clique hypothesis before invoking the core result.
- The pairwise distinctness of vertices in the 4-clique (lines 104–126) and the elementary set-theoretic pigeonhole lemmas (lines 4–30) are formal verification steps that would typically be taken as obvious on paper.
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 maxRecDepth 10000set_option maxHeartbeats 3000000private theorem two_of_inter_three {V : Type*} [DecidableEq V] (s : Finset V) (a b x : V) (h : 2 ≤ (s ∩ {a,b,x}).card) : (a ∈ s ∧ b ∈ s) ∨ (a ∈ s ∧ x ∈ s) ∨ (b ∈ s ∧ x ∈ s) := by classical by_contra hn have hle : (s ∩ {a,b,x}).card ≤ 1 := by apply Finset.card_le_one.mpr intro u hu v hv simp only [Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton] at hu hv aesop omegaprivate theorem third_vertex_of_three {V : Type*} [DecidableEq V] (s : Finset V) (a x : V) (hcard : s.card = 3) (ha : a ∈ s) (hx : x ∈ s) : ∃ y ∈ s, y ≠ a ∧ y ≠ x := by classical by_contra hn have hsub : s ⊆ {a,x} := by intro y hy simp only [not_exists, not_and] at hn simp only [Finset.mem_insert, Finset.mem_singleton] by_contra hn2 exact hn y hy (by aesop) (by aesop) have hc := Finset.card_le_card hsub have htwo := Finset.card_le_two (a := a) (b := x) omegatheorem two_covers_k4_attachment_core {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P Q : Finset (Finset V)) (a b c x : V) (hax : a ≠ x) (hbx : b ≠ x) (habx : G.IsNClique 3 ({a,b,x} : Finset V)) (hPcover : ∀ s : Finset V, G.IsNClique 3 s → ∃ t ∈ P, 2 ≤ (t ∩ s).card) (hQcover : ∀ s : Finset V, G.IsNClique 3 s → ∃ t ∈ Q, 2 ≤ (t ∩ s).card) (hQtri : ∀ t ∈ Q, G.IsNClique 3 t) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (havoid : ∀ t ∈ Q, ¬ (a ∈ t ∧ b ∈ t) ∧ ¬ (c ∈ t ∧ x ∈ t)) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset V) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset V) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y))) := by classical obtain ⟨q, hqQ, hmeet⟩ := hQcover {a,b,x} habx have hqcl := hQtri q hqQ have hqa := havoid q hqQ have hv : ∃ v : V, (v = a ∨ v = b) ∧ v ∈ q ∧ x ∈ q := by rcases two_of_inter_three q a b x hmeet with hab | hax | hbx · exact False.elim (hqa.1 hab) · exact ⟨a, Or.inl rfl, hax.1, hax.2⟩ · exact ⟨b, Or.inr rfl, hbx.1, hbx.2⟩ obtain ⟨v, hvab, hvq, hxq⟩ := hv have hvx : v ≠ x := by rcases hvab with rfl | rfl <;> assumption obtain ⟨y, hyq, hyv, hyx⟩ := third_vertex_of_three q v x hqcl.card_eq hvq hxq have hyoutside : y ∉ ({a,b,c,x} : Finset V) := by simp only [Finset.mem_insert, Finset.mem_singleton, not_or] rcases hvab with rfl | rfl <;> aesop have hqeq : ({v,x,y} : Finset V) = q := by apply Finset.eq_of_subset_of_card_le · simp [Finset.insert_subset, hvq, hxq, hyq] · have hcard : ({v,x,y} : Finset V).card = 3 := by simp [hvx, hyv, hyx, Ne.symm hvx, Ne.symm hyv, Ne.symm hyx] have hcq := hqcl.card_eq omega have hxy : G.Adj x y := hqcl.isClique hxq hyq (Ne.symm hyx) have hvy : G.Adj v y := hqcl.isClique hvq hyq (Ne.symm hyv) obtain ⟨t, htP, htp⟩ := hPcover q hqcl rw [← hqeq] at htp have hnotvx : ¬ (v ∈ t ∧ x ∈ t) := by rcases hvab with rfl | rfl · intro h; exact (hspokes t htP).1 ⟨h.2, h.1⟩ · intro h; exact (hspokes t htP).2 ⟨h.2, h.1⟩ have hyt : y ∈ t := by rcases two_of_inter_three t v x y htp with hvx' | hvy' | hxy' · exact False.elim (hnotvx hvx') · exact hvy'.2 · exact hxy'.2 have htne : t ≠ ({a,b,c} : Finset V) := by intro h apply hyoutside rw [h] at hyt simp only [Finset.mem_insert, Finset.mem_singleton] at hyt ⊢ aesop rcases two_of_inter_three t v x y htp with hvx' | hvy' | hxy' · exact False.elim (hnotvx hvx') · refine ⟨t, htP, htne, y, hvy'.2, hyoutside, Or.inl ⟨?_, hxy⟩⟩ rcases hvab with rfl | rfl <;> aesop · refine ⟨t, htP, htne, y, hxy'.2, hyoutside, Or.inr ⟨hxy'.1, ?_⟩⟩ rcases hvab with rfl | rfl <;> aesoptheorem two_covers_k4_attachment {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (P Q : Finset (Finset V)) (a b c x : V) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset V)) (hPcover : ∀ s : Finset V, G.IsNClique 3 s → ∃ t ∈ P, 2 ≤ (t ∩ s).card) (hQcover : ∀ s : Finset V, G.IsNClique 3 s → ∃ t ∈ Q, 2 ≤ (t ∩ s).card) (hQtri : ∀ t ∈ Q, G.IsNClique 3 t) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (havoid : ∀ t ∈ Q, ¬ (a ∈ t ∧ b ∈ t) ∧ ¬ (c ∈ t ∧ x ∈ t)) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset V) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset V) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y))) := by classical have hax : a ≠ x := by intro h; subst x have hsub : ({a,b,c,a} : Finset V) ⊆ {a,b,c} := by intro z hz; simp only [Finset.mem_insert, Finset.mem_singleton] at hz ⊢; aesop have hc := Finset.card_le_card hsub have h3 := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega have hbx : b ≠ x := by intro h; subst x have hsub : ({a,b,c,b} : Finset V) ⊆ {a,b,c} := by intro z hz; simp only [Finset.mem_insert, Finset.mem_singleton] at hz ⊢; aesop have hc := Finset.card_le_card hsub have h3 := Finset.card_le_three (a := a) (b := b) (c := c) have h4 := hk4.card_eq omega have hab : a ≠ b := by intro h; subst b have hsub : ({a,a,c,x} : Finset V) ⊆ {a,c,x} := by simp have hc := Finset.card_le_card hsub have h3 := Finset.card_le_three (a := a) (b := c) (c := x) have h4 := hk4.card_eq omega have habx : G.IsNClique 3 ({a,b,x} : Finset V) := by refine ⟨SimpleGraph.IsClique.subset ?_ hk4.isClique, ?_⟩ · intro z hz simp only [Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hz ⊢ aesop · simp [hab, hax, hbx, Ne.symm hab, Ne.symm hax, Ne.symm hbx] exact two_covers_k4_attachment_core G P Q a b c x hax hbx habx hPcover hQcover hQtri hspokes havoidtheorem simple_graph_k4_attachment_of_two_triangle_edge_covers (n : ℕ) (G : SimpleGraph (Fin n)) [DecidableRel G.Adj] (P Q : Finset (Finset (Fin n))) (a b c x : Fin n) (hk4 : G.IsNClique 4 ({a,b,c,x} : Finset (Fin n))) (hPcover : ∀ s : Finset (Fin n), G.IsNClique 3 s → ∃ t ∈ P, 2 ≤ (t ∩ s).card) (hQcover : ∀ s : Finset (Fin n), G.IsNClique 3 s → ∃ t ∈ Q, 2 ≤ (t ∩ s).card) (hQtri : ∀ t ∈ Q, G.IsNClique 3 t) (hspokes : ∀ t ∈ P, ¬ (x ∈ t ∧ a ∈ t) ∧ ¬ (x ∈ t ∧ b ∈ t)) (havoid : ∀ t ∈ Q, ¬ (a ∈ t ∧ b ∈ t) ∧ ¬ (c ∈ t ∧ x ∈ t)) : ∃ t ∈ P, t ≠ ({a,b,c} : Finset (Fin n)) ∧ ∃ y ∈ t, y ∉ ({a,b,c,x} : Finset (Fin n)) ∧ (((a ∈ t ∨ b ∈ t) ∧ G.Adj x y) ∨ (x ∈ t ∧ (G.Adj a y ∨ G.Adj b y))) := by exact two_covers_k4_attachment G P Q a b c x hk4 hPcover hQcover hQtri hspokes havoid