simple_graph_triangle_cover_reduces_to_separator_free
Given the two-vertex separator induction step, the triangle packing-cover inequality for all separator-free finite graphs implies it for all finite graphs.
Statement
theorem simple_graph_triangle_cover_reduces_to_separator_free (hstep : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) (A B : Finset V), A ∪ B = Finset.univ → A.card < Fintype.card V → B.card < Fintype.card V → (A ∩ B).card ≤ 2 → (∀ x ∈ A \ B, ∀ y ∈ B \ A, ¬ G.Adj x y) → (∀ (W : Type) [Fintype W] [DecidableEq W], Fintype.card W < Fintype.card V → ∀ H : SimpleGraph W, simple_graph_triangle_cover_number H ≤ 2 * simple_graph_triangle_packing_number H) → simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G) (hcore : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V), ¬ simple_graph_has_separator_of_order_two V G → simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G) : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V), simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G
- Source
- Induction assembly for the published separator reduction, https://www.cs.tau.ac.il/~krivelev/2.pdf, Lemma 5.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_has_separator_of_order_twoA finite graph has a proper vertex separation of order at most two when its vertices split between two proper sets with no edges between…
- 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).
The proof, explained
The proof proceeds by strong induction on the number of vertices |V| of the graph G. For the induction step, we branch on whether G has a 2-vertex separator. If G is separator-free, the triangle packing-cover inequality holds immediately by the base assumption hcore; if G has a 2-vertex separator, the reduction hypothesis hstep reduces the claim to strictly smaller graphs, which satisfy the inequality by the induction hypothesis.
We set up strong induction on the number of vertices n: it suffices to show that any graph G on a vertex set V with |V| = n satisfies the triangle cover inequality, assuming the inequality holds for all graphs on fewer than n vertices.
We enable classical reasoning (classical) and state an auxiliary lemma hall asserting that every graph on a vertex set of cardinality n satisfies the inequality. We then proceed by strong induction on n using Nat.strong_induction_on, yielding the induction hypothesis ih for all graphs with strictly fewer than n vertices. Finally, we introduce an arbitrary vertex set V of cardinality n and a graph G on V.
uses
Nat.strong_induction_onclassical have hall : ∀ n : ℕ, ∀ (V : Type) [Fintype V] [DecidableEq V], Fintype.card V = n → ∀ G : SimpleGraph V, simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G := by intro n induction n using Nat.strong_induction_on with | h n ih => intro V instV decV hcard G
If G has a separator of order at most 2, then the triangle cover inequality holds for G.
We split into cases on whether G has a 2-vertex separator (by_cases). In the positive case, we obtain two subsets A and B covering V with |A| < |V|, |B| < |V|, |A ∩ B| ≤ 2, and no edges between A \ B and B \ A. We then apply the reduction hypothesis hstep, which requires verifying that the inequality holds for all graphs H on vertex sets W strictly smaller than V. Since |W| < |V| = n, linear arithmetic (omega) confirms |W| < n, so the induction hypothesis ih applies to H.
by_cases h : simple_graph_has_separator_of_order_two V G · obtain ⟨A,B,hcover,hA,hB,hcardAB,hcross⟩ := h apply hstep V G A B hcover hA hB hcardAB hcross intro W instW decW hlt H apply ih (Fintype.card W) (by omega) W rfl H
If G does not have a separator of order at most 2, then the triangle cover inequality holds for G.
In the negative case where G has no 2-vertex separator, the core hypothesis hcore applies directly to G to close the goal.
· exact hcore V G hThe triangle cover inequality holds for all finite graphs.
Given any finite vertex set V and graph G on V, we specialize the established helper lemma hall to n = |V| and G to conclude the theorem.
intro V instV decV G exact hall (Fintype.card V) V rfl G
Nat.strong_induction_on- Strong induction on natural numbers: if a property holds for n whenever it holds for all m < n, then it holds for all n.
- The induction is formalized on an explicitly introduced natural number n representing the vertex count (|V| = n) to apply Lean's strong induction principle on natural numbers (Nat.strong_induction_on).
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.
theorem simple_graph_triangle_cover_reduces_to_separator_free (hstep : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V) (A B : Finset V), A ∪ B = Finset.univ → A.card < Fintype.card V → B.card < Fintype.card V → (A ∩ B).card ≤ 2 → (∀ x ∈ A \ B, ∀ y ∈ B \ A, ¬ G.Adj x y) → (∀ (W : Type) [Fintype W] [DecidableEq W], Fintype.card W < Fintype.card V → ∀ H : SimpleGraph W, simple_graph_triangle_cover_number H ≤ 2 * simple_graph_triangle_packing_number H) → simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G) (hcore : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V), ¬ simple_graph_has_separator_of_order_two V G → simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G) : ∀ (V : Type) [Fintype V] [DecidableEq V] (G : SimpleGraph V), simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G := by classical have hall : ∀ n : ℕ, ∀ (V : Type) [Fintype V] [DecidableEq V], Fintype.card V = n → ∀ G : SimpleGraph V, simple_graph_triangle_cover_number G ≤ 2 * simple_graph_triangle_packing_number G := by intro n induction n using Nat.strong_induction_on with | h n ih => intro V instV decV hcard G by_cases h : simple_graph_has_separator_of_order_two V G · obtain ⟨A,B,hcover,hA,hB,hcardAB,hcross⟩ := h apply hstep V G A B hcover hA hB hcardAB hcross intro W instW decW hlt H apply ih (Fintype.card W) (by omega) W rfl H · exact hcore V G h intro V instV decV G exact hall (Fintype.card V) V rfl G