AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_of_full_common_matching

theoremverified

If an edge common-neighbor graph has a matching as large as the graph triangle packing number, the triangle cover number is at most the packing number plus one.

Statement

theorem simple_graph_triangle_cover_of_full_common_matching
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    (u v : V) (M : Finset (Finset V))
    (huv : G.Adj u v)
    (hM : ∀ e ∈ M, e.card = 2 ∧ (∀ 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) :
    simple_graph_triangle_cover_number G ≤ M.card + 1
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 5

The proof, explained

The theorem establishes that if the common neighborhood of an edge uv contains a matching M whose size equals the triangle packing number ν(G), then the triangle cover number τ(G) is at most |M| + 1. Coning u and v over M creates two star-like triangle packings of size |M| = ν(G), which are therefore maximum triangle packings that meet every triangle of G in at least an edge. Letting C be the set of edges corresponding to M, every edge of a triangle in the u-packing (respectively v-packing) is incident to u (respectively v) or belongs to C. An auxiliary result for two star packings then shows that C ∪ {uv} covers all triangles in G, yielding τ(G) ≤ |C| + 1 ≤ |M| + 1.

  1. Each pair e ∈ M can be uniquely represented as {a(e), b(e)} for chosen distinct vertices a(e), b(e) ∈ V.

    Working in a classical setting where V is non-empty (witnessed by vertex u), each e ∈ M has cardinality 2 by hypothesis hM. By Finset.card_eq_two.mp, there exist distinct vertices a, b with e = {a, b}. The axiom of choice (choose!) extracts choice functions a, b : Finset V → V such that a(e) ≠ b(e) and e = {a(e), b(e)} for all e ∈ M.

    lines 14–19

    uses Finset.card_eq_two.mp

      classical
      letI : Nonempty V := ⟨u⟩
      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
  2. The set C of unordered pairs s(a(e), b(e)) for e ∈ M consists entirely of edges of G.

    For any edge f ∈ C, Finset.mem_image.mp shows that f = s(a(e), b(e)) for some e ∈ M. Since a(e) and b(e) are distinct elements of e = {a(e), b(e)}, the third clause of hM guarantees that they are adjacent in G, so f ∈ G.edgeSet.

    lines 20–30

    uses Finset.mem_image.mp

      let C : Finset (Sym2 V) := M.image (fun e => s(a e,b e))
      have hC : ∀ e ∈ C, e ∈ G.edgeSet := by
        intro f hf
        obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hf
        apply (hM e he).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
  3. For every e ∈ M and distinct x, y ∈ e, the unordered pair s(x, y) belongs to C.

    Since e = {a(e), b(e)}, both x and y must equal either a(e) or b(e) (by Finset.mem_insert and Finset.mem_singleton). Because x ≠ y, they cannot be identical; thus either (x, y) = (a(e), b(e)), giving s(x, y) ∈ C directly via Finset.mem_image.mpr, or (x, y) = (b(e), a(e)), which also belongs to C by symmetry of unordered pairs (Sym2.eq_swap).

    lines 31–44

    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) ∈ C := Finset.mem_image.mpr ⟨e, he, rfl⟩
        rcases hx' with rfl | rfl <;> rcases hy' with rfl | rfl
        · exact (hxy rfl).elim
        · exact hmem
        · simpa [Sym2.eq_swap] using hmem
        · exact (hxy rfl).elim
  4. For any vertex z and any triangle s = e ∪ {z} with e ∈ M, every pair of distinct vertices x, y ∈ s satisfies x = z, y = z, or s(x, y) ∈ C.

    Let s = e ∪ {z} for e ∈ M (via Finset.mem_image.mp). For distinct x, y ∈ s, each is either z or an element of e by Finset.mem_insert. Case analysis shows that if x = z or y = z, the disjunction holds immediately (via Or.inl, Or.inr). Otherwise, both x and y belong to e, so s(x, y) ∈ C by the property proved in the previous step.

    lines 45–54

    uses Finset.mem_image.mp, Finset.mem_insert, Or.inl, Or.inr

      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))
  5. Coning u and v over M yields two maximum triangle packings, each sharing an edge with every triangle in G.

    Hypothesis hM implies that M is a matching in the link of u and in the link of v. By simple_graph_matching_link_star_packing, coning u (respectively v) over M produces a triangle packing P (respectively Q) of size |M| whose triangles pairwise share at most one vertex. Because |M| equals the triangle packing number ν(G), P and Q are maximum packings. By simple_graph_maximum_triangle_packing_edge_meets, every maximum packing must intersect every triangle of G in at least two vertices (an edge).

    lines 55–68

    uses simple_graph_matching_link_star_packing, simple_graph_maximum_triangle_packing_edge_meets

      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.1 x hx).1), (hM e he).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.1 x hx).2), (hM e he).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 huMax := simple_graph_maximum_triangle_packing_edge_meets G _ huP.1 huP.2.1
        (by rw [huP.2.2, hnum])
      have hvMax := simple_graph_maximum_triangle_packing_edge_meets G _ hvP.1 hvP.2.1
        (by rw [hvP.2.2, hnum])
  6. The triangle cover number of G is at most |M| + 1.

    Applying simple_graph_triangle_cover_of_two_star_packings with the edge uv, the packings P and Q, and the edge set C shows that the triangle cover number is at most |C| + 1. Since C is the image of M under an edge-construction map, |C| ≤ |M| by Finset.card_image_le. Linear arithmetic (omega) finishes the proof by concluding that the cover number is at most |M| + 1.

    lines 69–72

    uses simple_graph_triangle_cover_of_two_star_packings, Finset.card_image_le

      have hcover := simple_graph_triangle_cover_of_two_star_packings G u v _ _ C huv hC
        huMax hvMax (hstar u) (hstar v)
      have hcard : C.card ≤ M.card := Finset.card_image_le
      omega
Finset.card_image_le
The cardinality of the image of a finite set under a function is at most the cardinality of the domain set.
Finset.card_eq_two.mp
A finite set has cardinality 2 if and only if it consists of two distinct elements.
Finset.mem_image.mp
If an element belongs to the image of a set under a function, then it is the image of some element of that set.
Finset.mem_image.mpr
If an element is the image of a member of a set, then it belongs to the image of that set.
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 {a} if and only if it equals a.
Or.inl
From a proof of P, deduces P ∨ Q.
Or.inr
From a proof of Q, deduces P ∨ Q.
Sym2.eq_swap
The unordered pair s(a, b) equals s(b, a).
simple_graph_matching_link_star_packing
A matching in the link of a vertex z yields a family of pairwise edge-disjoint triangles (sharing only z) of the same cardinality.
simple_graph_maximum_triangle_packing_edge_meets
Every maximum triangle packing in a graph shares at least two vertices (an edge) with every triangle in the graph.
simple_graph_triangle_cover_of_two_star_packings
If u and v are adjacent and P, Q are triangle packings meeting every triangle in an edge, such that all edges not incident to u (resp. v) lie in an edge set C, then the triangle cover number is at most |C| + 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_full_common_matching    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    (u v : V) (M : Finset (Finset V))    (huv : G.Adj u v)    (hM : ∀ e ∈ M, e.card = 2 ∧ (∀ 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) :    simple_graph_triangle_cover_number G ≤ M.card + 1 := by  classical  letI : Nonempty V := ⟨u⟩  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 C : Finset (Sym2 V) := M.image (fun e => s(a e,b e))  have hC : ∀ e ∈ C, e ∈ G.edgeSet := by    intro f hf    obtain ⟨e, he, rfl⟩ := Finset.mem_image.mp hf    apply (hM e he).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 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) ∈ C := Finset.mem_image.mpr ⟨e, he, rfl⟩    rcases hx' with rfl | rfl <;> rcases hy' with rfl | rfl    · exact (hxy rfl).elim    · exact hmem    · simpa [Sym2.eq_swap] using hmem    · exact (hxy rfl).elim  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 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.1 x hx).1), (hM e he).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.1 x hx).2), (hM e he).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 huMax := simple_graph_maximum_triangle_packing_edge_meets G _ huP.1 huP.2.1    (by rw [huP.2.2, hnum])  have hvMax := simple_graph_maximum_triangle_packing_edge_meets G _ hvP.1 hvP.2.1    (by rw [hvP.2.2, hnum])  have hcover := simple_graph_triangle_cover_of_two_star_packings G u v _ _ C huv hC    huMax hvMax (hstar u) (hstar v)  have hcard : C.card ≤ M.card := Finset.card_image_le  omega
See it in the graphDiscuss this resultChallenge it