AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_number_le_three_mul_packing_number

theoremverifiedformalization

Every finite graph satisfies τ(G) ≤ 3ν(G): the edges of a maximum family of edge-disjoint triangles meet every triangle.

Statement

theorem simple_graph_triangle_cover_number_le_three_mul_packing_number {V : Type*} [Fintype V]
    [DecidableEq V] (G : SimpleGraph V) :
    simple_graph_triangle_cover_number G ≤ 3 * simple_graph_triangle_packing_number G
Formalizes
The trivial bound ν(G) ≤ τ(G) ≤ 3ν(G), recalled in arXiv:2610.15539 (Tuza's conjecture under an edge-count condition), Sec. 1 (display after Conjecture 1.1); the bound Tuza's conjecture improves to 2ν.
Verified
14 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

To prove τ(G) ≤ 3ν(G), we choose a maximum family T of pairwise edge-disjoint triangles in G, so that |T| = ν(G). Let F be the set of all edges of the triangles in T; then |F| ≤ 3|T| = 3ν(G). By the maximality of T, every triangle in G must share at least two vertices with some triangle in T, meaning that it contains at least one edge of that triangle. Thus F is an edge cover of all triangles in G, which implies τ(G) ≤ |F| ≤ 3ν(G).

  1. If the vertex set V is empty, the theorem holds trivially because there are no triangles.

    We case-split on whether V is empty or nonempty using `isEmpty_or_nonempty`. When V is empty, any triangle (3-clique) would have 3 vertices in an empty set, yielding 0 = 3 via `Finset.card_empty` and `Finset.eq_empty_of_isEmpty`, an arithmetic contradiction. Thus G has no triangles, so `simple_graph_triangle_cover_number_eq_zero_of_clique_free` shows τ(G) = 0, and 0 ≤ 3ν(G) holds by `Nat.zero_le`.

    lines 4–10

    uses isEmpty_or_nonempty, simple_graph_triangle_cover_number_eq_zero_of_clique_free, Finset.eq_empty_of_isEmpty, Finset.card_empty, Nat.zero_le

      classical
      rcases isEmpty_or_nonempty V with hV | hV
      · rw [simple_graph_triangle_cover_number_eq_zero_of_clique_free G (fun t ht => by
            have := ht.card_eq
            rw [Finset.eq_empty_of_isEmpty t, Finset.card_empty] at this
            omega)]
        exact Nat.zero_le _
  2. There exists a maximum family T of pairwise edge-disjoint triangles in G, with |T| = ν(G).

    We define P to be the set of sizes of all collections of pairwise edge-disjoint triangles in G. The set P is bounded above by the total number of vertex subsets via `Finset.card_le_univ`, and nonempty because the empty family ∅ has size 0. By `Nat.sSup_mem`, P contains its supremum. Letting T be a packing achieving this maximum size, we have |T| = ν(G), and by `le_csSup`, any other edge-disjoint triangle packing has size at most |T|.

    lines 11–23

    uses Finset.card_le_univ, Nat.sSup_mem, le_csSup

      set P : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ t ∈ T, G.IsNClique 3 t) ∧
        (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} with hP
      have hbdd : BddAbove P := by
        refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩
        rintro n ⟨T, -, -, rfl⟩
        exact Finset.card_le_univ T
      have hne : P.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩
      obtain ⟨T, hT, hTp, hTc⟩ := Nat.sSup_mem hne hbdd
      have hmax : ∀ T' : Finset (Finset V), (∀ t ∈ T', G.IsNClique 3 t) →
          (T' : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) → T'.card ≤ T.card := by
        intro T' h1 h2
        rw [hTc]
        exact le_csSup hbdd ⟨T', h1, h2, rfl⟩
  3. Each triangle in T consists of three distinct vertices, and F is defined as the union of the edges of all triangles in T.

    Every triangle t ∈ T has cardinality 3, so by `Finset.card_eq_three.1`, it can be written as {x, y, z} with x, y, z pairwise distinct. By `choose!`, we extract vertex choice functions fx, fy, fz. We then define E(t) to be the set of the three edges of t, and F to be the union of E(t) over all t ∈ T.

    lines 24–31

    uses Finset.card_eq_three.1

      -- three edges of each triangle
      have h3 : ∀ t ∈ T, ∃ x y z : V, x ≠ y ∧ x ≠ z ∧ y ≠ z ∧ t = {x, y, z} := by
        intro t ht
        exact Finset.card_eq_three.1 (hT t ht).card_eq
      choose! fx fy fz hxy hxz hyz hxyz using h3
      set E : Finset V → Finset (Sym2 V) :=
        fun t => {s(fx t, fy t), s(fy t, fz t), s(fx t, fz t)} with hE
      set F := T.biUnion E with hF
  4. The candidate edge cover F has cardinality at most 3|T|.

    By subadditivity of the union (`Finset.card_biUnion_le`), |F| ≤ ∑_{t ∈ T} |E(t)|. Each E(t) is defined by three vertex insertions, so |E(t)| ≤ 3 by `Finset.card_insert_le` and `Nat.succ_le_succ`. Summing this upper bound over all t ∈ T using `Finset.sum_le_sum` gives |F| ≤ ∑_{t ∈ T} 3 = 3|T| via `Finset.sum_const`, `smul_eq_mul`, and `mul_comm`.

    lines 32–40

    uses Finset.card_biUnion_le, Finset.sum_le_sum, Finset.card_insert_le, Nat.succ_le_succ, Finset.sum_const, smul_eq_mul, mul_comm

      have hFcard : F.card ≤ 3 * T.card := by
        calc F.card ≤ ∑ t ∈ T, (E t).card := Finset.card_biUnion_le
          _ ≤ ∑ _t ∈ T, 3 := by
              apply Finset.sum_le_sum
              intro t _
              simp only [hE]
              exact (Finset.card_insert_le _ _).trans
                (Nat.succ_le_succ ((Finset.card_insert_le _ _).trans (by simp)))
          _ = 3 * T.card := by rw [Finset.sum_const, smul_eq_mul, mul_comm]
  5. Every element of F is an edge of the graph G.

    Any edge e ∈ F belongs to E(t) for some triangle t ∈ T by `Finset.mem_biUnion`. The three vertices fx(t), fy(t), fz(t) belong to t. Since t is a 3-clique in G, every pair of distinct vertices in t is adjacent in G. Checking each of the three edges in E(t) using `Finset.mem_insert` and `Finset.mem_singleton`, we find that e is an edge of G.

    lines 41–57

    uses Finset.mem_biUnion, Finset.mem_insert, Finset.mem_singleton

      have hFedge : ∀ e ∈ F, e ∈ G.edgeSet := by
        intro e he
        simp only [hF, Finset.mem_biUnion] at he
        obtain ⟨t, ht, he⟩ := he
        have hcl := (hT t ht).isClique
        have hsub : ∀ x ∈ ({fx t, fy t, fz t} : Finset V), x ∈ t := by
          intro x hx
          rw [← hxyz t ht] at hx
          exact hx
        have hx : fx t ∈ t := hsub _ (by simp)
        have hy : fy t ∈ t := hsub _ (by simp)
        have hz : fz t ∈ t := hsub _ (by simp)
        simp only [hE, Finset.mem_insert, Finset.mem_singleton] at he
        rcases he with rfl | rfl | rfl
        · exact hcl hx hy (hxy t ht)
        · exact hcl hy hz (hyz t ht)
        · exact hcl hx hz (hxz t ht)
  6. Any two distinct vertices of a triangle s ∈ T form one of its three edges in E(s).

    Since s = {fx(s), fy(s), fz(s)}, any distinct vertices u, w ∈ s are two distinct vertices among fx(s), fy(s), fz(s). A case analysis on all pairs, using symmetry of unordered pairs (`Sym2.eq_swap`), confirms that the unordered pair {u, w} is in E(s).

    lines 58–67

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

      -- every pair of distinct vertices of a packing triangle spans one of its three edges
      have hpair : ∀ s ∈ T, ∀ u ∈ s, ∀ w ∈ s, u ≠ w → s(u, w) ∈ E s := by
        intro s hs u hu w hw huw
        rw [hxyz s hs] at hu hw
        simp only [Finset.mem_insert, Finset.mem_singleton] at hu hw
        simp only [hE, Finset.mem_insert, Finset.mem_singleton]
        rcases hu with rfl | rfl | rfl <;> rcases hw with rfl | rfl | rfl <;>
          first
          | exact absurd rfl huw
          | simp [Sym2.eq_swap]
  7. The edge set F covers every triangle in G: every triangle contains at least one edge from F.

    Let t be a triangle in G. If t shared at most one vertex with every triangle s ∈ T, then t could not already be in T (since |t ∩ t| = 3 by `Finset.inter_self`), and T ∪ {t} would be a pairwise edge-disjoint packing of size |T| + 1 by `Finset.card_insert_of_notMem`. This would contradict the maximality of T. Hence some triangle s ∈ T must share at least two vertices with t: |s ∩ t| ≥ 2. By `Finset.one_lt_card.1`, s ∩ t contains two distinct vertices u and w. Then {u, w} is an edge in E(s) ⊆ F whose endpoints both lie in t.

    lines 68–102

    uses Finset.inter_self, Finset.mem_insert.1, Finset.coe_insert, Finset.inter_comm, Finset.card_insert_of_notMem, Finset.one_lt_card.1, Finset.mem_inter, Finset.mem_biUnion.2, Sym2.mem_iff

      have hcover : ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t := by
        intro t ht
        -- some packing triangle shares two vertices with `t`
        have : ∃ s ∈ T, 2 ≤ (s ∩ t).card := by
          by_contra hno
          push_neg at hno
          have htT : t ∉ T := by
            intro htT
            have := hno t htT
            rw [Finset.inter_self, ht.card_eq] at this
            omega
          have h1 : ∀ s ∈ insert t T, G.IsNClique 3 s := by
            intro s hs
            rcases Finset.mem_insert.1 hs with rfl | hs
            · exact ht
            · exact hT s hs
          have h2 : ((insert t T : Finset (Finset V)) : Set (Finset V)).Pairwise
              (fun s t => (s ∩ t).card ≤ 1) := by
            rw [Finset.coe_insert]
            refine hTp.insert ?_
            intro s hs _
            have := hno s hs
            exact ⟨by rw [Finset.inter_comm]; omega, by omega⟩
          have := hmax _ h1 h2
          rw [Finset.card_insert_of_notMem htT] at this
          omega
        obtain ⟨s, hs, hst⟩ := this
        obtain ⟨u, hu, w, hw, huw⟩ := Finset.one_lt_card.1 hst
        rw [Finset.mem_inter] at hu hw
        refine ⟨s(u, w), Finset.mem_biUnion.2 ⟨s, hs, hpair s hs u hu.1 w hw.1 huw⟩, ?_⟩
        intro x hx
        rw [Sym2.mem_iff] at hx
        rcases hx with rfl | rfl
        · exact hu.2
        · exact hw.2
  8. The triangle cover number satisfies τ(G) ≤ 3ν(G).

    Since F is a valid triangle cover of G, the minimum cover size τ(G) is at most |F| by `Nat.sInf_le`. Chaining this with |F| ≤ 3|T| and |T| = ν(G) yields τ(G) ≤ 3ν(G).

    lines 103–107

    uses Nat.sInf_le

      calc simple_graph_triangle_cover_number G ≤ F.card :=
            Nat.sInf_le ⟨F, hFedge, hcover, rfl⟩
        _ ≤ 3 * T.card := hFcard
        _ = 3 * simple_graph_triangle_packing_number G := by
            rw [hTc]; rfl
isEmpty_or_nonempty
Every type is either empty or nonempty.
simple_graph_triangle_cover_number_eq_zero_of_clique_free
If a simple graph contains no triangles (is 3-clique free), its triangle cover number is 0.
Finset.eq_empty_of_isEmpty
Any finite set over an empty type is the empty set.
Finset.card_empty
The cardinality of the empty set is 0.
Nat.zero_le
0 is less than or equal to any natural number.
Finset.card_le_univ
The cardinality of any finite subset is at most the cardinality of the full finite type.
Nat.sSup_mem
A nonempty set of natural numbers that is bounded above contains its supremum (maximum).
le_csSup
Any element in a bounded-above set is at most the supremum of the set.
Finset.card_eq_three.1
If a finite set has cardinality 3, then it consists of three pairwise distinct elements.
Finset.card_biUnion_le
The cardinality of a union of finite sets is at most the sum of their individual cardinalities.
Finset.sum_le_sum
A sum of terms is bounded by the sum of termwise upper bounds.
Finset.card_insert_le
Inserting an element into a finite set increases its cardinality by at most 1.
Nat.succ_le_succ
If n ≤ m, then n + 1 ≤ m + 1.
Finset.sum_const
Summing a constant over a finite set equals the cardinality of the set times the constant.
smul_eq_mul
Scalar multiplication of natural numbers coincides with ordinary multiplication.
mul_comm
Multiplication of natural numbers is commutative.
Finset.mem_biUnion
An element belongs to a union of sets ⋃_{a ∈ s} t(a) if and only if it belongs to t(a) for some a ∈ s.
Finset.mem_insert
An element belongs to {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.
Sym2.eq_swap
An unordered pair is symmetric: s(a, b) = s(b, a).
Finset.inter_self
The intersection of a finite set with itself is the set itself.
Finset.mem_insert.1
If an element belongs to {a} ∪ s, it equals a or belongs to s.
Finset.coe_insert
The coercion of {a} ∪ s to a set equals the set insertion of a into the coercion of s.
Finset.inter_comm
Intersection of finite sets is commutative.
Finset.card_insert_of_notMem
Inserting an element not already in a finite set increases its cardinality by 1.
Finset.one_lt_card.1
If a finite set has cardinality strictly greater than 1, it contains two distinct elements.
Finset.mem_inter
An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
Finset.mem_biUnion.2
If an element belongs to t(a) for some a ∈ s, it belongs to ⋃_{a ∈ s} t(a).
Sym2.mem_iff
A vertex x is an endpoint of an unordered pair s(a, b) if and only if x = a or x = b.
Nat.sInf_le
If a natural number belongs to a set, it is an upper bound on the infimum of that set.

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

theorem simple_graph_triangle_cover_number_le_three_mul_packing_number {V : Type*} [Fintype V]    [DecidableEq V] (G : SimpleGraph V) :    simple_graph_triangle_cover_number G ≤ 3 * simple_graph_triangle_packing_number G := by  classical  rcases isEmpty_or_nonempty V with hV | hV  · rw [simple_graph_triangle_cover_number_eq_zero_of_clique_free G (fun t ht => by        have := ht.card_eq        rw [Finset.eq_empty_of_isEmpty t, Finset.card_empty] at this        omega)]    exact Nat.zero_le _  set P : Set ℕ := {n | ∃ T : Finset (Finset V), (∀ t ∈ T, G.IsNClique 3 t) ∧    (T : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) ∧ T.card = n} with hP  have hbdd : BddAbove P := by    refine ⟨(Finset.univ : Finset (Finset V)).card, ?_⟩    rintro n ⟨T, -, -, rfl⟩    exact Finset.card_le_univ T  have hne : P.Nonempty := ⟨0, ∅, by simp, by simp, rfl⟩  obtain ⟨T, hT, hTp, hTc⟩ := Nat.sSup_mem hne hbdd  have hmax : ∀ T' : Finset (Finset V), (∀ t ∈ T', G.IsNClique 3 t) →      (T' : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1) → T'.card ≤ T.card := by    intro T' h1 h2    rw [hTc]    exact le_csSup hbdd ⟨T', h1, h2, rfl⟩  -- three edges of each triangle  have h3 : ∀ t ∈ T, ∃ x y z : V, x ≠ y ∧ x ≠ z ∧ y ≠ z ∧ t = {x, y, z} := by    intro t ht    exact Finset.card_eq_three.1 (hT t ht).card_eq  choose! fx fy fz hxy hxz hyz hxyz using h3  set E : Finset V → Finset (Sym2 V) :=    fun t => {s(fx t, fy t), s(fy t, fz t), s(fx t, fz t)} with hE  set F := T.biUnion E with hF  have hFcard : F.card ≤ 3 * T.card := by    calc F.card ≤ ∑ t ∈ T, (E t).card := Finset.card_biUnion_le      _ ≤ ∑ _t ∈ T, 3 := by          apply Finset.sum_le_sum          intro t _          simp only [hE]          exact (Finset.card_insert_le _ _).trans            (Nat.succ_le_succ ((Finset.card_insert_le _ _).trans (by simp)))      _ = 3 * T.card := by rw [Finset.sum_const, smul_eq_mul, mul_comm]  have hFedge : ∀ e ∈ F, e ∈ G.edgeSet := by    intro e he    simp only [hF, Finset.mem_biUnion] at he    obtain ⟨t, ht, he⟩ := he    have hcl := (hT t ht).isClique    have hsub : ∀ x ∈ ({fx t, fy t, fz t} : Finset V), x ∈ t := by      intro x hx      rw [← hxyz t ht] at hx      exact hx    have hx : fx t ∈ t := hsub _ (by simp)    have hy : fy t ∈ t := hsub _ (by simp)    have hz : fz t ∈ t := hsub _ (by simp)    simp only [hE, Finset.mem_insert, Finset.mem_singleton] at he    rcases he with rfl | rfl | rfl    · exact hcl hx hy (hxy t ht)    · exact hcl hy hz (hyz t ht)    · exact hcl hx hz (hxz t ht)  -- every pair of distinct vertices of a packing triangle spans one of its three edges  have hpair : ∀ s ∈ T, ∀ u ∈ s, ∀ w ∈ s, u ≠ w → s(u, w) ∈ E s := by    intro s hs u hu w hw huw    rw [hxyz s hs] at hu hw    simp only [Finset.mem_insert, Finset.mem_singleton] at hu hw    simp only [hE, Finset.mem_insert, Finset.mem_singleton]    rcases hu with rfl | rfl | rfl <;> rcases hw with rfl | rfl | rfl <;>      first      | exact absurd rfl huw      | simp [Sym2.eq_swap]  have hcover : ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F, ∀ x ∈ e, x ∈ t := by    intro t ht    -- some packing triangle shares two vertices with `t`    have : ∃ s ∈ T, 2 ≤ (s ∩ t).card := by      by_contra hno      push_neg at hno      have htT : t ∉ T := by        intro htT        have := hno t htT        rw [Finset.inter_self, ht.card_eq] at this        omega      have h1 : ∀ s ∈ insert t T, G.IsNClique 3 s := by        intro s hs        rcases Finset.mem_insert.1 hs with rfl | hs        · exact ht        · exact hT s hs      have h2 : ((insert t T : Finset (Finset V)) : Set (Finset V)).Pairwise          (fun s t => (s ∩ t).card ≤ 1) := by        rw [Finset.coe_insert]        refine hTp.insert ?_        intro s hs _        have := hno s hs        exact ⟨by rw [Finset.inter_comm]; omega, by omega⟩      have := hmax _ h1 h2      rw [Finset.card_insert_of_notMem htT] at this      omega    obtain ⟨s, hs, hst⟩ := this    obtain ⟨u, hu, w, hw, huw⟩ := Finset.one_lt_card.1 hst    rw [Finset.mem_inter] at hu hw    refine ⟨s(u, w), Finset.mem_biUnion.2 ⟨s, hs, hpair s hs u hu.1 w hw.1 huw⟩, ?_⟩    intro x hx    rw [Sym2.mem_iff] at hx    rcases hx with rfl | rfl    · exact hu.2    · exact hw.2  calc simple_graph_triangle_cover_number G ≤ F.card :=        Nat.sInf_le ⟨F, hFedge, hcover, rfl⟩    _ ≤ 3 * T.card := hFcard    _ = 3 * simple_graph_triangle_packing_number G := by        rw [hTc]; rfl
See it in the graphDiscuss this resultChallenge it