simple_graph_triangle_free_independent_cover_capacity
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.
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.
classical let P : α → Finset α := fun t => S.filter (fun x => G.Adj t x ∧ ∀ y ∈ J t, ¬ G.Adj x y)
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.
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_complhave 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
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.
uses
Finset.sum_le_sum,Finset.sum_add_distrib,mul_commhave 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
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.
uses
Finset.mem_biUnion.mpr,Finset.mem_filter.mprhave 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⟩
|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.
uses
Finset.card_le_card,Finset.card_biUnion_lehave hsize : S.card ≤ ∑ t ∈ T, (P t).card := (Finset.card_le_card hS).trans Finset.card_biUnion_le|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.
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
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_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