simple_graph_edge_reduction_inequality
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
- simple_graph_triangle_packing_number_ge_of_edge_reductionLet 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…
- simple_graph_triangle_cover_number_le_of_edge_reductionLet 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…
- finite_vertex_set_edge_encodingThe non-diagonal unordered vertex pairs spanned by a finite vertex set.
- simple_graph_triangle_cover_numberτ(G): the minimum number of edges of G such that every triangle of G contains one of them.
- simple_graph_triangle_packing_numberν(G): the maximum number of pairwise edge-disjoint triangles of G (two triangles are edge-disjoint when they share at most one vertex).
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|.
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).
uses
simple_graph_triangle_packing_number_ge_of_edge_reductionintro 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
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|.
uses
simple_graph_triangle_cover_number_le_of_edge_reductionhave 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 hESThe 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|.
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|.
- The final inequality is verified by the `omega` decision procedure, which automatically handles Presburger arithmetic over natural numbers including truncating subtraction.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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