AFTD Auto-Formalizing Theoretical Domains

simple_graph_edge_reduction_inequality

theoremverifiedformalization

Let G be a finite simple graph. Suppose there exist a nonempty edge set F ⊆ E(G), a set S of pairwise edge-disjoint triangles of G, and an edge set X ⊆ E(G) such that X meets every triangle of G containing an edge of F, E(S) \ F ⊆ X, and |X| ≤ 2|S|. Let G' = G \ (F ∪ X). Then ν(G') + |S| ≤ ν(G), τ(G) ≤ τ(G') + |X|, and τ(G) - 2ν(G) ≤ τ(G') - 2ν(G').

Statement

open Classical in
theorem simple_graph_edge_reduction_inequality
    {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)
    (hXcard : X.card ≤ 2 * S.card) :
    let G' := G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))
    simple_graph_triangle_packing_number G' + S.card ≤ simple_graph_triangle_packing_number G ∧
    simple_graph_triangle_cover_number G ≤ simple_graph_triangle_cover_number G' + X.card ∧
    simple_graph_triangle_cover_number G - 2 * simple_graph_triangle_packing_number G ≤
      simple_graph_triangle_cover_number G' - 2 * simple_graph_triangle_packing_number G'
Formalizes
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 5

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$. Assume: 1. $F$ is a nonempty finite set of edges of $G$ ($F \subseteq G.\text{edgeFinset}$ and $F.\text{Nonempty}$). 2. $S$ is a finite set of 3-cliques (triangles) of $G$ ($\forall t \in S, G.\text{IsNClique } 3\ t$). 3. The elements of $S$ are pairwise almost disjoint: for any distinct $s, t \in S$, $|s \cap t| \le 1$ (meaning they share at most one vertex, hence are edge-disjoint). 4. $X$ is a finite set of edges of $G$ ($X \subseteq G.\text{edgeFinset}$). 5. For every 3-clique $t$ of $G$, if $t$ contains an edge of $F$ (i.e., $\exists e \in F, \forall x \in e, x \in t$), then $t$ also contains an edge of $X$ (i.e., $\exists e \in X, \forall x \in e, x \in t$). 6. Every edge belonging to a triangle in $S$ that is not in $F$ is in $X$, i.e., $(\bigcup_{t \in S} \{ e \in t^{(2)} \mid \neg e.\text{IsDiag} \}) \setminus F \subseteq X$. 7. The cardinality of $X$ is at most $2|S|$ ($|X| \le 2|S|$). Let $G'$ be the simple graph obtained from $G$ by deleting all edges in $F \cup X$ ($G' = G.\text{deleteEdges}(F \cup X)$). Then the following three inequalities hold: 1. $\nu(G') + |S| \le \nu(G)$, where $\nu$ is the triangle packing number of a graph; 2. $\tau(G) \le \tau(G') + |X|$, where $\tau$ is the triangle cover number of a graph; 3. $\tau(G) - 2 \nu(G) \le \tau(G') - 2 \nu(G')$, where subtraction is truncated subtraction on $\mathbb{N}$.

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

The proof establishes Tuza's reduction inequality for triangle packing and covering numbers. The first two inequalities—bounding the change in triangle packing number ν from below by |S| and the change in triangle cover number τ from above by |X|—are imported from two companion reduction lemmas. The third inequality, τ(G) - 2ν(G) ≤ τ(G') - 2ν(G'), is then deduced purely by linear arithmetic using the assumption |X| ≤ 2|S|.

  1. Defining G' = G \ (F ∪ X), the triangle packing number satisfies ν(G') + |S| ≤ ν(G).

    We introduce the reduced graph G' obtained by deleting the edges in F ∪ X from G. Applying simple_graph_triangle_packing_number_ge_of_edge_reduction with the given hypotheses on F, S, and X shows that the triangle packing number decreases by at least |S|, giving ν(G') + |S| ≤ ν(G).

    lines 18–20

    uses simple_graph_triangle_packing_number_ge_of_edge_reduction

      intro G'
      have h1 : simple_graph_triangle_packing_number G' + S.card ≤ simple_graph_triangle_packing_number G :=
        simple_graph_triangle_packing_number_ge_of_edge_reduction G F hF hFne S hS hSpairwise X hX hXmeets hES
  2. The triangle cover number satisfies τ(G) ≤ τ(G') + |X|.

    Applying simple_graph_triangle_cover_number_le_of_edge_reduction shows that any triangle cover of G' together with X covers all triangles of G, yielding τ(G) ≤ τ(G') + |X|.

    lines 21–22

    uses simple_graph_triangle_cover_number_le_of_edge_reduction

      have h2 : simple_graph_triangle_cover_number G ≤ simple_graph_triangle_cover_number G' + X.card :=
        simple_graph_triangle_cover_number_le_of_edge_reduction G F hF hFne S hS hSpairwise X hX hXmeets hES
  3. The three inequalities hold simultaneously, in particular τ(G) - 2ν(G) ≤ τ(G') - 2ν(G'). automation

    We supply the first two bounds to the conjunction. After unfolding the definition of G', the linear arithmetic tactic omega concludes the third inequality from τ(G) ≤ τ(G') + |X|, ν(G') + |S| ≤ ν(G), and the hypothesis |X| ≤ 2|S|.

    lines 23–25

      refine ⟨h1, h2, ?_⟩
      dsimp [G'] at *
      omega
simple_graph_triangle_packing_number_ge_of_edge_reduction
Under the reduction hypotheses, deleting F ∪ X from G reduces the triangle packing number by at least |S|, so ν(G \ (F ∪ X)) + |S| ≤ ν(G).
simple_graph_triangle_cover_number_le_of_edge_reduction
Under the reduction hypotheses, the triangle cover number of G is at most that of G \ (F ∪ X) plus |X|, so τ(G) ≤ τ(G \ (F ∪ X)) + |X|.

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 Classical in/-- Edge-reduction inequality for triangle packing and covering (Lemma 2.2). -/theorem simple_graph_edge_reduction_inequality    {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)    (hXcard : X.card ≤ 2 * S.card) :    let G' := G.deleteEdges (↑(F ∪ X) : Set (Sym2 V))    simple_graph_triangle_packing_number G' + S.card ≤ simple_graph_triangle_packing_number G ∧    simple_graph_triangle_cover_number G ≤ simple_graph_triangle_cover_number G' + X.card ∧    simple_graph_triangle_cover_number G - 2 * simple_graph_triangle_packing_number G ≤      simple_graph_triangle_cover_number G' - 2 * simple_graph_triangle_packing_number G' := by  intro G'  have h1 : simple_graph_triangle_packing_number G' + S.card ≤ simple_graph_triangle_packing_number G :=    simple_graph_triangle_packing_number_ge_of_edge_reduction G F hF hFne S hS hSpairwise X hX hXmeets hES  have h2 : simple_graph_triangle_cover_number G ≤ simple_graph_triangle_cover_number G' + X.card :=    simple_graph_triangle_cover_number_le_of_edge_reduction G F hF hFne S hS hSpairwise X hX hXmeets hES  refine ⟨h1, h2, ?_⟩  dsimp [G'] at *  omega
See it in the graphDiscuss this resultChallenge it