AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_free_independent_cover_capacity

theoremverified

In a finite triangle-free graph with no independent k-set, let S and T be disjoint finite vertex sets. For each t in T let J(t) be an independent subset of T. If every vertex x in S has a neighbor t in T such that x has no neighbor in J(t), then |S| plus the sum of the sizes of the J(t) is at most (k − 1)|T|.

Statement

theorem simple_graph_triangle_free_independent_cover_capacity {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj]
    (k : ℕ) (htri : G.CliqueFree 3) (hfree : Gᶜ.CliqueFree k)
    (S T : Finset α) (J : α → Finset α) (hST : Disjoint S T)
    (hJsub : ∀ t ∈ T, J t ⊆ T)
    (hJind : ∀ t ∈ T, G.IsIndepSet (J t))
    (hcover : ∀ x ∈ S, ∃ t ∈ T, G.Adj t x ∧ ∀ y ∈ J t, ¬ G.Adj x y) :
    S.card + (∑ t ∈ T, (J t).card) ≤ (k - 1) * T.card
Source
Independent-set covering route for OP-926; the sets associated with t lie in its independent neighborhood.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

For each t ∈ T, we let P(t) ⊆ S consist of those vertices in S adjacent to t with no neighbors in J(t). Because G is triangle-free, the neighborhood of t is independent, which together with the independence of J(t) and the absence of edges between P(t) and J(t) implies that P(t) ∪ J(t) is an independent set; since G has no independent k-set, this gives |P(t)| + |J(t)| ≤ k − 1. Summing this bound over all t ∈ T gives ∑ |P(t)| + ∑ |J(t)| ≤ (k − 1)|T|, and since every vertex of S belongs to some P(t) by the covering assumption, |S| ≤ ∑ |P(t)|, completing the proof.

  1. For each t, define P(t) ⊆ S as the set of vertices in S adjacent to t with no neighbor in J(t).

    We enable classical logic and define the assignment P(t) = {x ∈ S | G.Adj t x ∧ ∀ y ∈ J(t), ¬ G.Adj x y}, partitioning the covering responsibility among elements of T.

    lines 8–9

      classical
      let P : α → Finset α := fun t => S.filter (fun x => G.Adj t x ∧ ∀ y ∈ J t, ¬ G.Adj x y)
  2. For each t ∈ T, |P(t)| + |J(t)| < k.

    For any t ∈ T, P(t) and J(t) are disjoint because P(t) ⊆ S, J(t) ⊆ T, and S and T are disjoint (using Finset.disjoint_left.mpr and Finset.disjoint_left.mp). Since G is triangle-free, the open neighborhood of t is an independent set, so its subset P(t) is independent. Furthermore, J(t) is independent by hypothesis, and by definition of P(t) no vertex in P(t) is adjacent to any vertex in J(t). A case analysis on pairs in P(t) ∪ J(t) (rewriting with Finset.coe_union and Set.mem_union) shows that P(t) ∪ J(t) is an independent set in G. If its size were at least k, then by Finset.card_union_of_disjoint and Finset.exists_subset_card_eq it would contain an independent set of size k, which is a k-clique in Gᶜ by SimpleGraph.isClique_compl, contradicting the assumption that Gᶜ is k-clique-free. Therefore, |P(t)| + |J(t)| < k.

    lines 10–37

    uses Finset.disjoint_left.mpr, Finset.disjoint_left.mp, Finset.coe_union, Set.mem_union, Finset.card_union_of_disjoint, Finset.exists_subset_card_eq, SimpleGraph.isClique_compl

      have hpoint (t : α) (ht : t ∈ T) : (P t).card + (J t).card < k := by
        have hdisj : Disjoint (P t) (J t) := by
          apply Finset.disjoint_left.mpr
          intro x hx hy
          exact (Finset.disjoint_left.mp hST) ((Finset.mem_filter.mp hx).1) ((hJsub t ht) hy)
        have hPi : G.IsIndepSet (P t) := by
          apply (G.isIndepSet_neighborSet_of_triangleFree htri t).mono
          intro x hx
          exact ((Finset.mem_filter.mp hx).2).1
        have hU : G.IsIndepSet ((P t ∪ J t : Finset α) : Set α) := by
          intro x hx y hy hxy
          simp only [Finset.coe_union, Set.mem_union] at hx hy
          rcases hx with hx | hx <;> rcases hy with hy | hy
          · exact hPi hx hy hxy
          · exact fun h => ((Finset.mem_filter.mp hx).2).2 y hy h
          · exact fun h => ((Finset.mem_filter.mp hy).2).2 x hx h.symm
          · exact hJind t ht hx hy hxy
        by_contra hn
        have hlarge : k ≤ (P t ∪ J t).card := by
          rw [Finset.card_union_of_disjoint hdisj]
          omega
        obtain ⟨u, hus, huc⟩ := Finset.exists_subset_card_eq hlarge
        apply hfree u
        apply (Gᶜ.isNClique_iff).2
        constructor
        · rw [SimpleGraph.isClique_compl]
          exact hU.mono (by exact_mod_cast hus)
        · exact huc
  3. The total sum of sizes satisfies ∑_{t ∈ T} |P(t)| + ∑_{t ∈ T} |J(t)| ≤ (k - 1)|T|.

    Since |P(t)| + |J(t)| < k for each t ∈ T, we have |P(t)| + |J(t)| ≤ k - 1. Summing this inequality over all t ∈ T with Finset.sum_le_sum gives ∑_{t ∈ T} (|P(t)| + |J(t)|) ≤ ∑_{t ∈ T} (k - 1). Distributing the sum on the left with Finset.sum_add_distrib and evaluating the constant sum on the right as (k - 1)|T| using mul_comm yields the inequality.

    lines 38–44

    uses Finset.sum_le_sum, Finset.sum_add_distrib, mul_comm

      have hsum : (∑ t ∈ T, ((P t).card + (J t).card)) ≤ ∑ _t ∈ T, (k - 1) := by
        apply Finset.sum_le_sum
        intro t ht
        have hp := hpoint t ht
        omega
      have hsum' : (∑ t ∈ T, (P t).card) + (∑ t ∈ T, (J t).card) ≤ (k - 1) * T.card := by
        simpa [Finset.sum_add_distrib, mul_comm] using hsum
  4. S is covered by the union of the sets P(t) over t ∈ T.

    By the covering hypothesis, every x ∈ S has a neighbor t ∈ T with no neighbors in J(t), which means x satisfies the defining predicate of P(t) (Finset.mem_filter.mpr). Thus x ∈ ⋃_{t ∈ T} P(t) by Finset.mem_biUnion.mpr.

    lines 45–50

    uses Finset.mem_biUnion.mpr, Finset.mem_filter.mpr

      have hS : S ⊆ T.biUnion P := by
        intro x hx
        obtain ⟨t, ht, hadj, hcross⟩ := hcover x hx
        apply Finset.mem_biUnion.mpr
        refine ⟨t, ht, ?_⟩
        exact Finset.mem_filter.mpr ⟨hx, hadj, hcross⟩
  5. |S| ≤ ∑_{t ∈ T} |P(t)|.

    Because S ⊆ ⋃_{t ∈ T} P(t), the cardinality of S is bounded by that of the union (Finset.card_le_card), which is in turn at most the sum of the cardinalities ∑_{t ∈ T} |P(t)| by the union bound Finset.card_biUnion_le.

    lines 51–52

    uses Finset.card_le_card, Finset.card_biUnion_le

      have hsize : S.card ≤ ∑ t ∈ T, (P t).card :=
        (Finset.card_le_card hS).trans Finset.card_biUnion_le
  6. |S| + ∑_{t ∈ T} |J(t)| ≤ (k - 1)|T|.

    Combining |S| ≤ ∑_{t ∈ T} |P(t)| with ∑_{t ∈ T} |P(t)| + ∑_{t ∈ T} |J(t)| ≤ (k - 1)|T| closes the goal by linear arithmetic.

    line 53

      omega
Finset.disjoint_left.mpr
If no element of s belongs to t, then s and t are disjoint.
Finset.disjoint_left.mp
If two finite sets are disjoint, no element of the first set belongs to the second set.
Finset.coe_union
The coercion of the union of two finite sets to a set equals the union of their coercions.
Set.mem_union
An element belongs to the union of two sets if and only if it belongs to at least one of them.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.exists_subset_card_eq
If a finite set has size at least n, it contains a subset of size exactly n.
SimpleGraph.isClique_compl
A set of vertices is a clique in the complement graph if and only if it is an independent set in the graph.
Finset.sum_le_sum
If f(i) ≤ g(i) for all i in a finite set, the sum of f over the set is at most the sum of g over the set.
Finset.sum_add_distrib
The sum of a sum over a finite set equals the sum of the two separate sums.
mul_comm
Multiplication is commutative: a * b = b * a.
Finset.mem_biUnion.mpr
An element belongs to an indexed union of finite sets if it belongs to one of the indexed sets.
Finset.mem_filter.mpr
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.card_le_card
A subset of a finite set has cardinality at most that of the ambient set.
Finset.card_biUnion_le
The cardinality of an indexed union of finite sets is at most the sum of the cardinalities of the sets.

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_free_independent_cover_capacity {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj]    (k : ℕ) (htri : G.CliqueFree 3) (hfree : Gᶜ.CliqueFree k)    (S T : Finset α) (J : α → Finset α) (hST : Disjoint S T)    (hJsub : ∀ t ∈ T, J t ⊆ T)    (hJind : ∀ t ∈ T, G.IsIndepSet (J t))    (hcover : ∀ x ∈ S, ∃ t ∈ T, G.Adj t x ∧ ∀ y ∈ J t, ¬ G.Adj x y) :    S.card + (∑ t ∈ T, (J t).card) ≤ (k - 1) * T.card := by  classical  let P : α → Finset α := fun t => S.filter (fun x => G.Adj t x ∧ ∀ y ∈ J t, ¬ G.Adj x y)  have hpoint (t : α) (ht : t ∈ T) : (P t).card + (J t).card < k := by    have hdisj : Disjoint (P t) (J t) := by      apply Finset.disjoint_left.mpr      intro x hx hy      exact (Finset.disjoint_left.mp hST) ((Finset.mem_filter.mp hx).1) ((hJsub t ht) hy)    have hPi : G.IsIndepSet (P t) := by      apply (G.isIndepSet_neighborSet_of_triangleFree htri t).mono      intro x hx      exact ((Finset.mem_filter.mp hx).2).1    have hU : G.IsIndepSet ((P t ∪ J t : Finset α) : Set α) := by      intro x hx y hy hxy      simp only [Finset.coe_union, Set.mem_union] at hx hy      rcases hx with hx | hx <;> rcases hy with hy | hy      · exact hPi hx hy hxy      · exact fun h => ((Finset.mem_filter.mp hx).2).2 y hy h      · exact fun h => ((Finset.mem_filter.mp hy).2).2 x hx h.symm      · exact hJind t ht hx hy hxy    by_contra hn    have hlarge : k ≤ (P t ∪ J t).card := by      rw [Finset.card_union_of_disjoint hdisj]      omega    obtain ⟨u, hus, huc⟩ := Finset.exists_subset_card_eq hlarge    apply hfree u    apply (Gᶜ.isNClique_iff).2    constructor    · rw [SimpleGraph.isClique_compl]      exact hU.mono (by exact_mod_cast hus)    · exact huc  have hsum : (∑ t ∈ T, ((P t).card + (J t).card)) ≤ ∑ _t ∈ T, (k - 1) := by    apply Finset.sum_le_sum    intro t ht    have hp := hpoint t ht    omega  have hsum' : (∑ t ∈ T, (P t).card) + (∑ t ∈ T, (J t).card) ≤ (k - 1) * T.card := by    simpa [Finset.sum_add_distrib, mul_comm] using hsum  have hS : S ⊆ T.biUnion P := by    intro x hx    obtain ⟨t, ht, hadj, hcross⟩ := hcover x hx    apply Finset.mem_biUnion.mpr    refine ⟨t, ht, ?_⟩    exact Finset.mem_filter.mpr ⟨hx, hadj, hcross⟩  have hsize : S.card ≤ ∑ t ∈ T, (P t).card :=    (Finset.card_le_card hS).trans Finset.card_biUnion_le  omega
See it in the graphDiscuss this resultChallenge it