AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_number_le_of_edge_reduction

theoremverified

Let G be a finite simple graph, F a nonempty edge subset, S a pairwise edge-disjoint triangle family, and X an edge subset such that X meets every triangle containing an edge of F and E(S) \ F ⊆ X. Then the triangle cover number of G is at most that of G \ (F ∪ X) plus |X|.

Statement

open Classical in
theorem simple_graph_triangle_cover_number_le_of_edge_reduction
    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)
    (F : Finset (Sym2 V)) (hF : F ⊆ G.edgeFinset) (hFne : F.Nonempty)
    (S : Finset (Finset V)) (hS : ∀ t ∈ S, G.IsNClique 3 t)
    (hSpairwise : (S : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1))
    (X : Finset (Sym2 V)) (hX : X ⊆ G.edgeFinset)
    (hXmeets : ∀ t : Finset V, G.IsNClique 3 t →
      (∃ e ∈ F, ∀ x ∈ e, x ∈ t) → ∃ e ∈ X, ∀ x ∈ e, x ∈ t)
    (hES : (S.biUnion finite_vertex_set_edge_encoding \ F) ⊆ X) :
    simple_graph_triangle_cover_number G ≤
      simple_graph_triangle_cover_number (G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))) + X.card
Source
arXiv:2611.11128 Lemma 2.2 -- Triangle-overlap cores and density bounds for Tuza's conjecture
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$. Let $F$ be a nonempty finite set of edges of $G$. Let $S$ be a finite set of 3-cliques of $G$ such that any two distinct cliques in $S$ share at most 1 vertex (i.e., $|s \cap t| \le 1$). Let $X$ be a finite set of edges of $G$ satisfying: 1. For every 3-clique $t$ of $G$, if $t$ contains an edge of $F$ (an edge whose endpoints both belong to $t$), then $t$ also contains an edge of $X$. 2. All edges spanned by cliques in $S$ that are not in $F$ belong to $X$ (i.e., $(\bigcup_{s \in S} E(s)) \setminus F \subseteq X$, where $E(s)$ is the set of unordered pairs of distinct vertices in $s$). Then the triangle cover number of $G$ is at most the triangle cover number of the graph obtained by deleting all edges in $F \cup X$ from $G$, plus $|X|$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To bound the triangle cover number $\tau_3(G)$, we delete the edges $F \cup X$ to form $H = G \setminus (F \cup X)$. Since the full edge set of $H$ is a trivial triangle cover, the set of cover sizes is nonempty, so $H$ admits a minimum triangle cover $C$ with $|C| = \tau_3(H)$. We then show that $C \cup X$ is a valid triangle cover of $G$: any triangle in $G$ either remains a clique in $H$ (hence covered by $C$) or contains an edge deleted into $F \cup X$, which by assumption or directly yields a covering edge in $X$. Since $C \cup X \subseteq E(G)$ covers all triangles of $G$, subadditivity gives $\tau_3(G) \le |C \cup X| \le |C| + |X| = \tau_3(H) + |X|$.

  1. For any finite simple graph $H$, the set of cardinalities of triangle covers is nonempty.

    We show that the full edge set $E(H)$ (`H.edgeFinset`) forms a valid triangle cover of $H$. First, every edge in `H.edgeFinset` belongs to $E(H)$ (SimpleGraph.mem_edgeFinset). Second, any triangle $t$ in $H$ has cardinality 3 (Finset.card_eq_three.mp), so $t = \{u, v, w\}$ with $u \ne v$. Since $t$ is a clique, the pair $\{u, v\}$ is an edge of $H$ (SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet), and both of its vertices lie in $t$ (Sym2.mem_iff). Thus $E(H)$ meets every triangle of $H$, showing the set of triangle cover sizes is nonempty.

    lines 5–15

    uses SimpleGraph.mem_edgeFinset, Finset.card_eq_three.mp, SimpleGraph.mem_edgeSet, Sym2.mem_iff

      classical
      refine ⟨_, H.edgeFinset, ?_, ?_, rfl⟩
      · intro f hf; rwa [SimpleGraph.mem_edgeFinset] at hf
      · intro t ht
        obtain ⟨u, v, w, huv, -, -, rfl⟩ := Finset.card_eq_three.mp ht.card_eq
        refine ⟨s(u, v), ?_, ?_⟩
        · rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]
          exact ht.isClique (by simp) (by simp) huv
        · intro x hx
          rw [Sym2.mem_iff] at hx
          rcases hx with rfl | rfl <;> simp
  2. Let $H = G \setminus (F \cup X)$; there exists a minimum triangle cover $C$ of $H$ with $|C| = \tau_3(H)$.

    We define the reduced graph $H$ by deleting the edges in $F \cup X$ from $G$. By simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty, the collection of cardinalities of triangle covers of $H$ is nonempty, so by Nat.sInf_mem its infimum is attained by some cover $C \subseteq E(H)$ whose size equals the triangle cover number $\tau_3(H)$.

    lines 30–33

    uses simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty, Nat.sInf_mem

      set H : SimpleGraph V := G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))
      obtain ⟨C, hCsub, hCcov, hCcard⟩ :=
        Nat.sInf_mem (simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty H)
      change C.card = simple_graph_triangle_cover_number H at hCcard
  3. Every edge in $C \cup X$ is an edge of $G$.

    For any $e \in C \cup X$ (Finset.mem_union), if $e \in C$, then $e \in E(H) = E(G) \setminus (F \cup X)$ by SimpleGraph.edgeSet_deleteEdges, so $e \in E(G)$. If $e \in X$, then $e \in E(G)$ by hypothesis $X \subseteq E(G)$ (SimpleGraph.mem_edgeFinset).

    lines 34–42

    uses Finset.mem_union, SimpleGraph.edgeSet_deleteEdges, SimpleGraph.mem_edgeFinset

      have hsubG : ∀ e ∈ C ∪ X, e ∈ G.edgeSet := by
        intro e he
        rw [Finset.mem_union] at he
        rcases he with heC | heX
        · have := hCsub e heC
          rw [SimpleGraph.edgeSet_deleteEdges] at this
          exact this.1
        · have := hX heX
          rwa [SimpleGraph.mem_edgeFinset] at this
  4. The edge set $C \cup X$ covers every triangle of $G$.

    Let $t$ be a triangle in $G$. We case-split on whether $t$ remains a clique in $H$. If $t$ is a clique in $H$, it is a triangle in $H$, so $C$ contains an edge of $t$, which is in $C \cup X$ (Finset.mem_union_left). If $t$ is not a clique in $H$ (SimpleGraph.isClique_iff, Set.Pairwise), there exist distinct vertices $u, v \in t$ not adjacent in $H$. Because they are adjacent in $G$, the edge $\{u, v\}$ must have been deleted, so $\{u, v\} \in F \cup X$ (SimpleGraph.deleteEdges_adj, Finset.mem_coe, Finset.mem_union). Both vertices lie in $t$ (Sym2.mem_iff). If $\{u, v\} \in F$, then by hypothesis hXmeets, $X$ contains an edge of $t$, which belongs to $C \cup X$ (Finset.mem_union_right). If $\{u, v\} \in X$, then $\{u, v\}$ itself is an edge of $t$ in $C \cup X$ (Finset.mem_union_right). In all cases, $C \cup X$ meets $t$.

    lines 43–64

    uses Finset.mem_union_left, SimpleGraph.isClique_iff, Set.Pairwise, SimpleGraph.deleteEdges_adj, Finset.mem_coe, Finset.mem_union, Sym2.mem_iff, Finset.mem_union_right

      have hcovG : ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ C ∪ X, ∀ x ∈ e, x ∈ t := by
        intro t ht
        by_cases hclq : H.IsClique (↑t : Set V)
        · obtain ⟨e, heC, het⟩ := hCcov t ⟨hclq, ht.card_eq⟩
          exact ⟨e, Finset.mem_union_left X heC, het⟩
        · rw [SimpleGraph.isClique_iff, Set.Pairwise] at hclq
          push Not at hclq
          obtain ⟨u, hu, v, hv, huv, hnotadj⟩ := hclq
          have hGadj : G.Adj u v := ht.isClique hu hv huv
          rw [SimpleGraph.deleteEdges_adj] at hnotadj
          have hdel : s(u, v) ∈ (↑(F ∪ X) : Set (Sym2 V)) := by
            by_contra h
            exact hnotadj ⟨hGadj, h⟩
          rw [Finset.mem_coe, Finset.mem_union] at hdel
          have hxuv : ∀ x ∈ s(u, v), x ∈ t := by
            intro x hx
            rw [Sym2.mem_iff] at hx
            rcases hx with rfl | rfl <;> assumption
          rcases hdel with hdelF | hdelX
          · obtain ⟨e, heX, het⟩ := hXmeets t ht ⟨s(u, v), hdelF, hxuv⟩
            exact ⟨e, Finset.mem_union_right C heX, het⟩
          · exact ⟨s(u, v), Finset.mem_union_right C hdelX, hxuv⟩
  5. The triangle cover number of $G$ is at most $\tau_3(G \setminus (F \cup X)) + |X|$.

    Because $C \cup X \subseteq E(G)$ meets every triangle in $G$, its size $|C \cup X|$ belongs to the set of triangle cover sizes of $G$. By definition of $\tau_3(G)$ as the infimum of this set, $\tau_3(G) \le |C \cup X|$ (Nat.sInf_le). By subadditivity of cardinality (Finset.card_union_le), $|C \cup X| \le |C| + |X| = \tau_3(H) + |X|$, which closes by linear arithmetic (omega). Transitivity of inequality yields the desired bound.

    lines 65–72

    uses Nat.sInf_le, Finset.card_union_le

      have hmemG : (C ∪ X).card ∈ {n : ℕ | ∃ F' : Finset (Sym2 V), (∀ e ∈ F', e ∈ G.edgeSet) ∧
          (∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F', ∀ x ∈ e, x ∈ t) ∧ F'.card = n} :=
        ⟨C ∪ X, hsubG, hcovG, rfl⟩
      have hle : simple_graph_triangle_cover_number G ≤ (C ∪ X).card := Nat.sInf_le hmemG
      have hcardle : (C ∪ X).card ≤ simple_graph_triangle_cover_number H + X.card := by
        have := Finset.card_union_le C X
        omega
      exact hle.trans hcardle
SimpleGraph.mem_edgeFinset
An edge belongs to the finite edge set of a graph if and only if it belongs to its edge set.
Finset.card_eq_three.mp
A finite set has cardinality 3 if and only if it consists of three distinct elements.
SimpleGraph.mem_edgeSet
An unordered pair of vertices belongs to the edge set of a graph if and only if the vertices are adjacent in the graph.
Sym2.mem_iff
A vertex $x$ belongs to the unordered pair $\{u, v\}$ if and only if $x = u$ or $x = v$.
simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty
For any finite simple graph, the set of cardinalities of its triangle covers is nonempty.
Nat.sInf_mem
If a set of natural numbers is nonempty, its infimum (minimum) belongs to the set.
Finset.mem_union
An element belongs to the union of two finite sets if and only if it belongs to at least one of them.
SimpleGraph.edgeSet_deleteEdges
The edge set of a graph after deleting a set of edges is the difference of the original edge set and the deleted set.
Finset.mem_union_left
An element of a finite set $s$ also belongs to the union $s \cup t$.
SimpleGraph.isClique_iff
A vertex set is a clique in a graph if and only if every pair of distinct vertices in it is adjacent.
Set.Pairwise
A binary relation holds for all pairs of distinct elements in a given set.
SimpleGraph.deleteEdges_adj
Two vertices are adjacent in a graph with deleted edges if and only if they were adjacent in the original graph and the edge between them was not deleted.
Finset.mem_coe
An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
Finset.mem_union_right
An element of a finite set $t$ also belongs to the union $s \cup t$.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element in the set.
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities.

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

lemma simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty    {V : Type*} [Fintype V] (H : SimpleGraph V) :    {n : ℕ | ∃ F : Finset (Sym2 V), (∀ f ∈ F, f ∈ H.edgeSet) ∧      (∀ t : Finset V, H.IsNClique 3 t → ∃ f ∈ F, ∀ x ∈ f, x ∈ t) ∧ F.card = n}.Nonempty := by  classical  refine ⟨_, H.edgeFinset, ?_, ?_, rfl⟩  · intro f hf; rwa [SimpleGraph.mem_edgeFinset] at hf  · intro t ht    obtain ⟨u, v, w, huv, -, -, rfl⟩ := Finset.card_eq_three.mp ht.card_eq    refine ⟨s(u, v), ?_, ?_⟩    · rw [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]      exact ht.isClique (by simp) (by simp) huv    · intro x hx      rw [Sym2.mem_iff] at hx      rcases hx with rfl | rfl <;> simpopen Classical in/-- Under an edge reduction (F, S, X), the triangle cover number of G is at most that of G \ (F ∪ X) plus |X|. -/theorem simple_graph_triangle_cover_number_le_of_edge_reduction    {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V)    (F : Finset (Sym2 V)) (hF : F ⊆ G.edgeFinset) (hFne : F.Nonempty)    (S : Finset (Finset V)) (hS : ∀ t ∈ S, G.IsNClique 3 t)    (hSpairwise : (S : Set (Finset V)).Pairwise (fun s t => (s ∩ t).card ≤ 1))    (X : Finset (Sym2 V)) (hX : X ⊆ G.edgeFinset)    (hXmeets : ∀ t : Finset V, G.IsNClique 3 t →      (∃ e ∈ F, ∀ x ∈ e, x ∈ t) → ∃ e ∈ X, ∀ x ∈ e, x ∈ t)    (hES : (S.biUnion finite_vertex_set_edge_encoding \ F) ⊆ X) :    simple_graph_triangle_cover_number G ≤      simple_graph_triangle_cover_number (G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))) + X.card := by  set H : SimpleGraph V := G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))  obtain ⟨C, hCsub, hCcov, hCcard⟩ :=    Nat.sInf_mem (simple_graph_triangle_cover_number_le_of_edge_reduction_cover_nonempty H)  change C.card = simple_graph_triangle_cover_number H at hCcard  have hsubG : ∀ e ∈ C ∪ X, e ∈ G.edgeSet := by    intro e he    rw [Finset.mem_union] at he    rcases he with heC | heX    · have := hCsub e heC      rw [SimpleGraph.edgeSet_deleteEdges] at this      exact this.1    · have := hX heX      rwa [SimpleGraph.mem_edgeFinset] at this  have hcovG : ∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ C ∪ X, ∀ x ∈ e, x ∈ t := by    intro t ht    by_cases hclq : H.IsClique (↑t : Set V)    · obtain ⟨e, heC, het⟩ := hCcov t ⟨hclq, ht.card_eq⟩      exact ⟨e, Finset.mem_union_left X heC, het⟩    · rw [SimpleGraph.isClique_iff, Set.Pairwise] at hclq      push Not at hclq      obtain ⟨u, hu, v, hv, huv, hnotadj⟩ := hclq      have hGadj : G.Adj u v := ht.isClique hu hv huv      rw [SimpleGraph.deleteEdges_adj] at hnotadj      have hdel : s(u, v) ∈ (↑(F ∪ X) : Set (Sym2 V)) := by        by_contra h        exact hnotadj ⟨hGadj, h⟩      rw [Finset.mem_coe, Finset.mem_union] at hdel      have hxuv : ∀ x ∈ s(u, v), x ∈ t := by        intro x hx        rw [Sym2.mem_iff] at hx        rcases hx with rfl | rfl <;> assumption      rcases hdel with hdelF | hdelX      · obtain ⟨e, heX, het⟩ := hXmeets t ht ⟨s(u, v), hdelF, hxuv⟩        exact ⟨e, Finset.mem_union_right C heX, het⟩      · exact ⟨s(u, v), Finset.mem_union_right C hdelX, hxuv⟩  have hmemG : (C ∪ X).card ∈ {n : ℕ | ∃ F' : Finset (Sym2 V), (∀ e ∈ F', e ∈ G.edgeSet) ∧      (∀ t : Finset V, G.IsNClique 3 t → ∃ e ∈ F', ∀ x ∈ e, x ∈ t) ∧ F'.card = n} :=    ⟨C ∪ X, hsubG, hcovG, rfl⟩  have hle : simple_graph_triangle_cover_number G ≤ (C ∪ X).card := Nat.sInf_le hmemG  have hcardle : (C ∪ X).card ≤ simple_graph_triangle_cover_number H + X.card := by    have := Finset.card_union_le C X    omega  exact hle.trans hcardle
See it in the graphDiscuss this resultChallenge it