AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_of_near_full_common_matching

theoremverified

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
Used by 1

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.

  1. 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.

    lines 15–19

      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
  2. 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₀.

    lines 20–25

    uses Finset.card_eq_two.mp

      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)
  3. 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.

    lines 26–42

    uses Finset.mem_image.mp, Finset.mem_insert

      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
  4. 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.

    lines 43–57

    uses Finset.mem_insert, Finset.mem_singleton, Finset.mem_image.mpr, Sym2.eq_swap

      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
  5. 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).

    lines 58–76

    uses SimpleGraph.isNClique_iff, Finset.mem_coe, Finset.mem_insert, Finset.mem_singleton, Ne.symm

      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⟩
  6. 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.

    lines 77–116

    uses simple_graph_matching_link_star_packing, Finset.mem_image.mp, Finset.mem_inter, Finset.mem_insert, Finset.mem_singleton, Finset.card_le_card

      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)
  7. 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.

    lines 117–122

    uses simple_graph_triangle_packing_insert_separated, simple_graph_maximum_triangle_packing_edge_meets

      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])
  8. 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.

    lines 123–156

    uses Finset.mem_image.mp, Finset.mem_insert, Or.inl, Or.inr, Finset.mem_insert.mp, Finset.mem_singleton, Sym2.eq_swap

      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
  9. 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.

    lines 157–165

    uses simple_graph_triangle_cover_of_two_star_packings, Finset.card_image_le, Finset.card_insert_le

      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
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

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
See it in the graphDiscuss this resultChallenge it