AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_cover_reduces_to_separator_free

theoremverified

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

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.

  1. 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.

    lines 15–22

    uses Nat.strong_induction_on

      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
  2. 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.

    lines 23–27

          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
  3. 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.

    line 28

          · exact hcore V G h
  4. The 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.

    lines 29–30

      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.

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_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
See it in the graphDiscuss this resultChallenge it