simple_graph_triangle_cover_of_near_full_common_matching
If an edge has a common-neighbor matching of size one below the graph triangle packing number and another common neighbor outside the matching, the triangle cover number is at most the packing number plus two.
Statement
theorem simple_graph_triangle_cover_of_near_full_common_matching {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (u v w : V) (M : Finset (Finset V)) (huv : G.Adj u v) (huw : G.Adj u w) (hvw : G.Adj v w) (hM : ∀ e ∈ M, e.card = 2 ∧ w ∉ e ∧ (∀ x ∈ e, G.Adj u x ∧ G.Adj v x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y)) (hdis : (M : Set (Finset V)).Pairwise Disjoint) (hnum : simple_graph_triangle_packing_number G = M.card + 1) : simple_graph_triangle_cover_number G ≤ M.card + 3
- Source
- Structural helper for the triangle packing-cover campaign; related matching-cover reductions are in https://arxiv.org/abs/2610.15269, Lemma 2.3. Finite checks and limitations are recorded in state/campaigns/triangle_reductions/high_codegree_route_in512.md.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- simple_graph_triangle_cover_numberτ(G): the minimum number of edges of G such that every triangle of G contains one of them.
- 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_maximum_triangle_packing_edge_meetsEvery triangle shares an edge with a member of a maximum edge-disjoint triangle packing.
- simple_graph_matching_link_star_packingDisjoint two-vertex edges in a vertex link yield a same-size edge-disjoint triangle packing through the vertex.
- simple_graph_triangle_packing_insert_separatedA triangle sharing at most one vertex with every member of an edge-disjoint triangle packing can be inserted, increasing the packing size…
- simple_graph_triangle_cover_of_two_star_packingsTwo triangle-maximal families whose non-star edges lie in C give a triangle cover of size at most |C|+1 if their star centers are adjacent.
- Used by 1
- simple_graph_triangle_cover_of_avoided_near_high_codegreeIf a maximum triangle packing avoids an edge with at least twice the packing number minus one common neighbors and the packing number is…
The proof, explained
The theorem is proved by constructing two maximum triangle packings centered at the adjacent vertices u and v, and applying the two-star packing theorem (simple_graph_triangle_cover_of_two_star_packings). Coning u and v over the matching M in their common neighborhood yields edge-disjoint triangle packings P and Q of size |M|, which are each extended to maximum packings of size |M| + 1 by including the triangle T = {u, v, w}. The candidate cover edge set C is defined as the |M| edges of M together with uw and vw, so |C| ≤ |M| + 2. Because every edge in P ∪ {T} not incident to u and every edge in Q ∪ {T} not incident to v belongs to C, the two-star packing theorem implies that the triangle cover number is at most |C| + 1 ≤ |M| + 3.
The vertices u, v, and w are pairwise distinct, and V is nonempty.
Since u, v, and w are pairwise adjacent (hypotheses huv, huw, hvw) and adjacent vertices in a simple graph cannot be equal, u ≠ v, u ≠ w, and v ≠ w. We also register that the vertex type V is inhabited by u.
classical letI : Nonempty V := ⟨u⟩ have huvne : u ≠ v := G.ne_of_adj huv have huwne : u ≠ w := G.ne_of_adj huw have hvwne : v ≠ w := G.ne_of_adj hvw
For each 2-element set e ∈ M, select its two endpoints a(e) ≠ b(e), and define edge sets C₀ = {s(a(e), b(e)) : e ∈ M} and C = C₀ ∪ {uw, vw}.
Every set e ∈ M has cardinality 2, so by Finset.card_eq_two.mp it equals {a(e), b(e)} for some distinct vertices a(e) ≠ b(e). We choose these endpoints for every e ∈ M and form C₀ by taking the unordered pair s(a(e), b(e)) for each e ∈ M, then define C by adjoining the edges uw and vw to C₀.
uses
Finset.card_eq_two.mphave hrep : ∀ e ∈ M, ∃ a b : V, a ≠ b ∧ e = {a,b} := by intro e he exact Finset.card_eq_two.mp (hM e he).1 choose! a b hab heq using hrep let C0 : Finset (Sym2 V) := M.image (fun e => s(a e,b e)) let C : Finset (Sym2 V) := insert s(u,w) (insert s(v,w) C0)
Every element of C₀, and consequently every element of C, is an edge of G.
For any edge f = s(a(e), b(e)) ∈ C₀, the distinct vertices a(e), b(e) ∈ e are adjacent by the hypothesis hM on M. Since C consists of C₀ together with uw and vw, which are edges of G by huw and hvw, all elements of C belong to G.edgeSet.
uses
Finset.mem_image.mp,Finset.mem_inserthave hC0 : ∀ e ∈ C0, e ∈ G.edgeSet := by intro f hf obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hf apply (hM e he).2.2.2 (a e) ?_ (b e) ?_ (hab e he) · have hmem : a e ∈ ({a e, b e} : Finset V) := by simp rw [← heq e he] at hmem exact hmem · have hmem : b e ∈ ({a e, b e} : Finset V) := by simp rw [← heq e he] at hmem exact hmem have hC : ∀ e ∈ C, e ∈ G.edgeSet := by intro f hf simp only [C, Finset.mem_insert] at hf rcases hf with rfl | rfl | hf · exact huw · exact hvw · exact hC0 f hf
For every e ∈ M and any distinct vertices x, y ∈ e, the edge s(x, y) belongs to C.
Because e = {a(e), b(e)}, any element of e is either a(e) or b(e). Since x ≠ y, the pair {x, y} is either (a(e), b(e)) or (b(e), a(e)). In either case, by symmetry of unordered pairs (Sym2.eq_swap), s(x, y) = s(a(e), b(e)) ∈ C₀ ⊆ C.
uses
Finset.mem_insert,Finset.mem_singleton,Finset.mem_image.mpr,Sym2.eq_swaphave hpair : ∀ e ∈ M, ∀ x ∈ e, ∀ y ∈ e, x ≠ y → s(x,y) ∈ C := by intro e he x hx y hy hxy have hx' : x = a e ∨ x = b e := by have hh : x ∈ ({a e,b e} : Finset V) := by rw [← heq e he]; exact hx simpa only [Finset.mem_insert, Finset.mem_singleton] using hh have hy' : y = a e ∨ y = b e := by have hh : y ∈ ({a e,b e} : Finset V) := by rw [← heq e he]; exact hy simpa only [Finset.mem_insert, Finset.mem_singleton] using hh have hmem : s(a e,b e) ∈ C0 := Finset.mem_image.mpr ⟨e, he, rfl⟩ have hmemC : s(a e,b e) ∈ C := by simp [C, hmem] rcases hx' with rfl | rfl <;> rcases hy' with rfl | rfl · exact (hxy rfl).elim · exact hmemC · simpa [Sym2.eq_swap] using hmemC · exact (hxy rfl).elim
The set T = {u, v, w} is a triangle (3-clique), and coning u and v over M yields families P and Q of triangles.
The vertices u, v, w are distinct and pairwise adjacent, so SimpleGraph.isNClique_iff confirms T = {u, v, w} is a 3-clique. We define P = {e ∪ {u} : e ∈ M} and Q = {e ∪ {v} : e ∈ M}, and extract from hM that every e ∈ M consists of an edge whose endpoints are adjacent to u (for P) and adjacent to v (for Q).
uses
SimpleGraph.isNClique_iff,Finset.mem_coe,Finset.mem_insert,Finset.mem_singleton,Ne.symmlet P : Finset (Finset V) := M.image (fun e => insert u e) let Q : Finset (Finset V) := M.image (fun e => insert v e) let T : Finset V := {u,v,w} have hT : G.IsNClique 3 T := by rw [SimpleGraph.isNClique_iff] constructor · intro x hx y hy hxy simp only [T, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hx hy rcases hx with rfl | rfl | rfl <;> rcases hy with rfl | rfl | rfl all_goals first | exact (hxy rfl).elim | exact huv | exact huv.symm | exact huw | exact huw.symm | exact hvw | exact hvw.symm · simp [T, huvne, huwne, hvwne, Ne.symm] have huM : ∀ e ∈ M, e.card = 2 ∧ (∀ x ∈ e, G.Adj u x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y) := by intro e he exact ⟨(hM e he).1, (fun x hx => ((hM e he).2.2.1 x hx).1), (hM e he).2.2.2⟩ have hvM : ∀ e ∈ M, e.card = 2 ∧ (∀ x ∈ e, G.Adj v x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y) := by intro e he exact ⟨(hM e he).1, (fun x hx => ((hM e he).2.2.1 x hx).2), (hM e he).2.2.2⟩
P and Q are triangle packings of size |M|, and each triangle in P or Q intersects T in at most one vertex.
By simple_graph_matching_link_star_packing, P and Q are pairwise edge-disjoint collections of |M| triangles. For any triangle s = e ∪ {u} ∈ P, the set e cannot contain v (as vertices in e are adjacent to v, which would violate irreflexivity) and does not contain w (by hM), so s ∩ T ⊆ {u}, showing |s ∩ T| ≤ 1. Symmetrically, each triangle in Q intersects T only within {v}, so |s ∩ T| ≤ 1.
uses
simple_graph_matching_link_star_packing,Finset.mem_image.mp,Finset.mem_inter,Finset.mem_insert,Finset.mem_singleton,Finset.card_le_cardhave huP := simple_graph_matching_link_star_packing G u M huM hdis have hvP := simple_graph_matching_link_star_packing G v M hvM hdis have huSep : ∀ s ∈ P, (s ∩ T).card ≤ 1 := by intro s hs obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hs have hvnot : v ∉ e := by intro hv exact G.irrefl (((hM e he).2.2.1 v hv).2) have hwnot : w ∉ e := (hM e he).2.1 have hsub : insert u e ∩ T ⊆ {u} := by intro x hx simp only [Finset.mem_inter, Finset.mem_insert, T, Finset.mem_singleton] at hx simp only [Finset.mem_singleton] rcases hx with ⟨hxU, hxT⟩ rcases hxU with rfl | hxE · rfl · rcases hxT with rfl | rfl | rfl · rfl · exact (hvnot hxE).elim · exact (hwnot hxE).elim exact (Finset.card_le_card hsub).trans (by simp) have hvSep : ∀ s ∈ Q, (s ∩ T).card ≤ 1 := by intro s hs obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hs have hunot : u ∉ e := by intro hu exact G.irrefl (((hM e he).2.2.1 u hu).1) have hwnot : w ∉ e := (hM e he).2.1 have hsub : insert v e ∩ T ⊆ {v} := by intro x hx simp only [Finset.mem_inter, Finset.mem_insert, T, Finset.mem_singleton] at hx simp only [Finset.mem_singleton] rcases hx with ⟨hxV, hxT⟩ rcases hxV with rfl | hxE · rfl · rcases hxT with rfl | rfl | rfl · exact (hunot hxE).elim · rfl · exact (hwnot hxE).elim exact (Finset.card_le_card hsub).trans (by simp)
The extended families P ∪ {T} and Q ∪ {T} are maximum triangle packings, so every triangle in G shares an edge with some member of each packing.
By simple_graph_triangle_packing_insert_separated, adjoining T to P and to Q preserves edge-disjointness and increases their size to |M| + 1. Since the packing number of G is |M| + 1 (hnum), both extended packings are maximum. By simple_graph_maximum_triangle_packing_edge_meets, every triangle in G must intersect at least one triangle in P ∪ {T} and at least one triangle in Q ∪ {T} in at least 2 vertices.
uses
simple_graph_triangle_packing_insert_separated,simple_graph_maximum_triangle_packing_edge_meetshave huP' := simple_graph_triangle_packing_insert_separated G P T huP.1 huP.2.1 hT huSep have hvP' := simple_graph_triangle_packing_insert_separated G Q T hvP.1 hvP.2.1 hT hvSep have huMax := simple_graph_maximum_triangle_packing_edge_meets G _ huP'.1 huP'.2.1 (by rw [huP'.2.2, huP.2.2, hnum]) have hvMax := simple_graph_maximum_triangle_packing_edge_meets G _ hvP'.1 hvP'.2.1 (by rw [hvP'.2.2, hvP.2.2, hnum])
Every edge of a triangle in P ∪ {T} not incident to u belongs to C, and every edge of a triangle in Q ∪ {T} not incident to v belongs to C.
For any triangle e ∪ {z} with e ∈ M, any two vertices either include z or are both in e, in which case their connecting edge is in C. For the triangle T = {u, v, w}, the edge not incident to u is vw ∈ C, and the edge not incident to v is uw ∈ C. Thus both packings exhibit the required star-like structure with respect to C.
uses
Finset.mem_image.mp,Finset.mem_insert,Or.inl,Or.inr,Finset.mem_insert.mp,Finset.mem_singleton,Sym2.eq_swaphave hstar : ∀ z : V, ∀ s ∈ M.image (fun e => insert z e), ∀ x ∈ s, ∀ y ∈ s, x ≠ y → x = z ∨ y = z ∨ s(x,y) ∈ C := by intro z s hs x hx y hy hxy obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hs simp only [Finset.mem_insert] at hx hy rcases hx with rfl | hx · exact Or.inl rfl · rcases hy with rfl | hy · exact Or.inr (Or.inl rfl) · exact Or.inr (Or.inr (hpair e he x hx y hy hxy)) have huStar : ∀ s ∈ insert T P, ∀ x ∈ s, ∀ y ∈ s, x ≠ y → x = u ∨ y = u ∨ s(x,y) ∈ C := by intro s hs x hx y hy hxy rcases Finset.mem_insert.mp hs with rfl | hs · simp only [T, Finset.mem_insert, Finset.mem_singleton] at hx hy rcases hx with rfl | rfl | rfl <;> rcases hy with rfl | rfl | rfl all_goals first | exact (hxy rfl).elim | exact Or.inl rfl | exact Or.inr (Or.inl rfl) | exact Or.inr (Or.inr (by simp [C, Sym2.eq_swap])) · exact hstar u s hs x hx y hy hxy have hvStar : ∀ s ∈ insert T Q, ∀ x ∈ s, ∀ y ∈ s, x ≠ y → x = v ∨ y = v ∨ s(x,y) ∈ C := by intro s hs x hx y hy hxy rcases Finset.mem_insert.mp hs with rfl | hs · simp only [T, Finset.mem_insert, Finset.mem_singleton] at hx hy rcases hx with rfl | rfl | rfl <;> rcases hy with rfl | rfl | rfl all_goals first | exact (hxy rfl).elim | exact Or.inl rfl | exact Or.inr (Or.inl rfl) | exact Or.inr (Or.inr (by simp [C, Sym2.eq_swap])) · exact hstar v s hs x hx y hy hxy
The triangle cover number of G is at most |M| + 3.
Applying simple_graph_triangle_cover_of_two_star_packings to the two maximum star packings centered at u and v gives simple_graph_triangle_cover_number G ≤ |C| + 1. Since |C₀| ≤ |M| (by Finset.card_image_le) and C is formed by adding at most two edges to C₀, |C| ≤ |C₀| + 2 ≤ |M| + 2 (by Finset.card_insert_le). Linear arithmetic (omega) combines these inequalities to conclude that the triangle cover number is at most |M| + 3.
uses
simple_graph_triangle_cover_of_two_star_packings,Finset.card_image_le,Finset.card_insert_lehave hc := simple_graph_triangle_cover_of_two_star_packings G u v _ _ C huv hC huMax hvMax huStar hvStar have hC0card : C0.card ≤ M.card := Finset.card_image_le have hCcard : C.card ≤ C0.card + 2 := by have h1 := Finset.card_insert_le s(v,w) C0 have h2 := Finset.card_insert_le s(u,w) (insert s(v,w) C0) change C.card ≤ _ at h2 omega omega
Finset.card_eq_two.mp- A finite set has cardinality 2 if and only if it consists of two distinct elements: #s = 2 → ∃ x y, x ≠ y ∧ s = {x, y}.
Finset.mem_image.mp- If y belongs to the image f '' s of a finset, then there exists some element x ∈ s such that f x = y.
Finset.mem_insert- An element belongs to insert a s if and only if it equals a or belongs to s.
Finset.mem_singleton- An element belongs to the singleton set {a} if and only if it equals a.
Finset.mem_image.mpr- If x ∈ s and f x = y, then y belongs to the image f '' s.
Sym2.eq_swap- The unordered pair of a and b equals the unordered pair of b and a: s(a, b) = s(b, a).
SimpleGraph.isNClique_iff- A finite set of vertices is an n-clique in G if and only if its elements are pairwise adjacent and its cardinality is n.
Finset.mem_coe- Membership of an element in the coerced set ↑s is equivalent to membership in the finset s.
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
simple_graph_matching_link_star_packing- Coning a vertex z over a pairwise disjoint matching M in its neighborhood yields a triangle packing of size |M|.
Finset.mem_inter- An element belongs to the intersection s₁ ∩ s₂ if and only if it belongs to both s₁ and s₂.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then #s ≤ #t.
simple_graph_triangle_packing_insert_separated- Adding a triangle t to a triangle packing P yields a triangle packing of size |P| + 1, provided t shares at most one vertex with each triangle in P.
simple_graph_maximum_triangle_packing_edge_meets- In any maximum triangle packing, every triangle in the graph shares at least two vertices (an edge) with some triangle in the packing.
Or.inl- From a proof of A, infer A ∨ B.
Or.inr- From a proof of B, infer A ∨ B.
Finset.mem_insert.mp- If x ∈ insert a s, then x = a or x ∈ s.
simple_graph_triangle_cover_of_two_star_packings- If two maximum triangle packings are stars centered at adjacent vertices u and v, and C is a set of graph edges containing all non-center edges of both packings, then the triangle cover number is at most |C| + 1.
Finset.card_image_le- The image of a finite set under any function has cardinality at most that of the domain: #(f '' s) ≤ #s.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1: #(insert a s) ≤ #s + 1.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem simple_graph_triangle_cover_of_near_full_common_matching {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) (u v w : V) (M : Finset (Finset V)) (huv : G.Adj u v) (huw : G.Adj u w) (hvw : G.Adj v w) (hM : ∀ e ∈ M, e.card = 2 ∧ w ∉ e ∧ (∀ x ∈ e, G.Adj u x ∧ G.Adj v x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y)) (hdis : (M : Set (Finset V)).Pairwise Disjoint) (hnum : simple_graph_triangle_packing_number G = M.card + 1) : simple_graph_triangle_cover_number G ≤ M.card + 3 := by classical letI : Nonempty V := ⟨u⟩ have huvne : u ≠ v := G.ne_of_adj huv have huwne : u ≠ w := G.ne_of_adj huw have hvwne : v ≠ w := G.ne_of_adj hvw have hrep : ∀ e ∈ M, ∃ a b : V, a ≠ b ∧ e = {a,b} := by intro e he exact Finset.card_eq_two.mp (hM e he).1 choose! a b hab heq using hrep let C0 : Finset (Sym2 V) := M.image (fun e => s(a e,b e)) let C : Finset (Sym2 V) := insert s(u,w) (insert s(v,w) C0) have hC0 : ∀ e ∈ C0, e ∈ G.edgeSet := by intro f hf obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hf apply (hM e he).2.2.2 (a e) ?_ (b e) ?_ (hab e he) · have hmem : a e ∈ ({a e, b e} : Finset V) := by simp rw [← heq e he] at hmem exact hmem · have hmem : b e ∈ ({a e, b e} : Finset V) := by simp rw [← heq e he] at hmem exact hmem have hC : ∀ e ∈ C, e ∈ G.edgeSet := by intro f hf simp only [C, Finset.mem_insert] at hf rcases hf with rfl | rfl | hf · exact huw · exact hvw · exact hC0 f hf have hpair : ∀ e ∈ M, ∀ x ∈ e, ∀ y ∈ e, x ≠ y → s(x,y) ∈ C := by intro e he x hx y hy hxy have hx' : x = a e ∨ x = b e := by have hh : x ∈ ({a e,b e} : Finset V) := by rw [← heq e he]; exact hx simpa only [Finset.mem_insert, Finset.mem_singleton] using hh have hy' : y = a e ∨ y = b e := by have hh : y ∈ ({a e,b e} : Finset V) := by rw [← heq e he]; exact hy simpa only [Finset.mem_insert, Finset.mem_singleton] using hh have hmem : s(a e,b e) ∈ C0 := Finset.mem_image.mpr ⟨e, he, rfl⟩ have hmemC : s(a e,b e) ∈ C := by simp [C, hmem] rcases hx' with rfl | rfl <;> rcases hy' with rfl | rfl · exact (hxy rfl).elim · exact hmemC · simpa [Sym2.eq_swap] using hmemC · exact (hxy rfl).elim let P : Finset (Finset V) := M.image (fun e => insert u e) let Q : Finset (Finset V) := M.image (fun e => insert v e) let T : Finset V := {u,v,w} have hT : G.IsNClique 3 T := by rw [SimpleGraph.isNClique_iff] constructor · intro x hx y hy hxy simp only [T, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton] at hx hy rcases hx with rfl | rfl | rfl <;> rcases hy with rfl | rfl | rfl all_goals first | exact (hxy rfl).elim | exact huv | exact huv.symm | exact huw | exact huw.symm | exact hvw | exact hvw.symm · simp [T, huvne, huwne, hvwne, Ne.symm] have huM : ∀ e ∈ M, e.card = 2 ∧ (∀ x ∈ e, G.Adj u x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y) := by intro e he exact ⟨(hM e he).1, (fun x hx => ((hM e he).2.2.1 x hx).1), (hM e he).2.2.2⟩ have hvM : ∀ e ∈ M, e.card = 2 ∧ (∀ x ∈ e, G.Adj v x) ∧ (∀ x ∈ e, ∀ y ∈ e, x ≠ y → G.Adj x y) := by intro e he exact ⟨(hM e he).1, (fun x hx => ((hM e he).2.2.1 x hx).2), (hM e he).2.2.2⟩ have huP := simple_graph_matching_link_star_packing G u M huM hdis have hvP := simple_graph_matching_link_star_packing G v M hvM hdis have huSep : ∀ s ∈ P, (s ∩ T).card ≤ 1 := by intro s hs obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hs have hvnot : v ∉ e := by intro hv exact G.irrefl (((hM e he).2.2.1 v hv).2) have hwnot : w ∉ e := (hM e he).2.1 have hsub : insert u e ∩ T ⊆ {u} := by intro x hx simp only [Finset.mem_inter, Finset.mem_insert, T, Finset.mem_singleton] at hx simp only [Finset.mem_singleton] rcases hx with ⟨hxU, hxT⟩ rcases hxU with rfl | hxE · rfl · rcases hxT with rfl | rfl | rfl · rfl · exact (hvnot hxE).elim · exact (hwnot hxE).elim exact (Finset.card_le_card hsub).trans (by simp) have hvSep : ∀ s ∈ Q, (s ∩ T).card ≤ 1 := by intro s hs obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hs have hunot : u ∉ e := by intro hu exact G.irrefl (((hM e he).2.2.1 u hu).1) have hwnot : w ∉ e := (hM e he).2.1 have hsub : insert v e ∩ T ⊆ {v} := by intro x hx simp only [Finset.mem_inter, Finset.mem_insert, T, Finset.mem_singleton] at hx simp only [Finset.mem_singleton] rcases hx with ⟨hxV, hxT⟩ rcases hxV with rfl | hxE · rfl · rcases hxT with rfl | rfl | rfl · exact (hunot hxE).elim · rfl · exact (hwnot hxE).elim exact (Finset.card_le_card hsub).trans (by simp) have huP' := simple_graph_triangle_packing_insert_separated G P T huP.1 huP.2.1 hT huSep have hvP' := simple_graph_triangle_packing_insert_separated G Q T hvP.1 hvP.2.1 hT hvSep have huMax := simple_graph_maximum_triangle_packing_edge_meets G _ huP'.1 huP'.2.1 (by rw [huP'.2.2, huP.2.2, hnum]) have hvMax := simple_graph_maximum_triangle_packing_edge_meets G _ hvP'.1 hvP'.2.1 (by rw [hvP'.2.2, hvP.2.2, hnum]) have hstar : ∀ z : V, ∀ s ∈ M.image (fun e => insert z e), ∀ x ∈ s, ∀ y ∈ s, x ≠ y → x = z ∨ y = z ∨ s(x,y) ∈ C := by intro z s hs x hx y hy hxy obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hs simp only [Finset.mem_insert] at hx hy rcases hx with rfl | hx · exact Or.inl rfl · rcases hy with rfl | hy · exact Or.inr (Or.inl rfl) · exact Or.inr (Or.inr (hpair e he x hx y hy hxy)) have huStar : ∀ s ∈ insert T P, ∀ x ∈ s, ∀ y ∈ s, x ≠ y → x = u ∨ y = u ∨ s(x,y) ∈ C := by intro s hs x hx y hy hxy rcases Finset.mem_insert.mp hs with rfl | hs · simp only [T, Finset.mem_insert, Finset.mem_singleton] at hx hy rcases hx with rfl | rfl | rfl <;> rcases hy with rfl | rfl | rfl all_goals first | exact (hxy rfl).elim | exact Or.inl rfl | exact Or.inr (Or.inl rfl) | exact Or.inr (Or.inr (by simp [C, Sym2.eq_swap])) · exact hstar u s hs x hx y hy hxy have hvStar : ∀ s ∈ insert T Q, ∀ x ∈ s, ∀ y ∈ s, x ≠ y → x = v ∨ y = v ∨ s(x,y) ∈ C := by intro s hs x hx y hy hxy rcases Finset.mem_insert.mp hs with rfl | hs · simp only [T, Finset.mem_insert, Finset.mem_singleton] at hx hy rcases hx with rfl | rfl | rfl <;> rcases hy with rfl | rfl | rfl all_goals first | exact (hxy rfl).elim | exact Or.inl rfl | exact Or.inr (Or.inl rfl) | exact Or.inr (Or.inr (by simp [C, Sym2.eq_swap])) · exact hstar v s hs x hx y hy hxy have hc := simple_graph_triangle_cover_of_two_star_packings G u v _ _ C huv hC huMax hvMax huStar hvStar have hC0card : C0.card ≤ M.card := Finset.card_image_le have hCcard : C.card ≤ C0.card + 2 := by have h1 := Finset.card_insert_le s(v,w) C0 have h2 := Finset.card_insert_le s(u,w) (insert s(v,w) C0) change C.card ≤ _ at h2 omega omega