simple_graph_triangle_free_independent_neighborhood_cover
In a finite triangle-free graph with no independent set of size k, let s be an independent set all of whose vertices are non-neighbors of v, and let t be the neighbors of v having no neighbors in s. Then |s| + |t| < k.
Statement
theorem simple_graph_triangle_free_independent_neighborhood_cover {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] (k : ℕ) (htri : G.CliqueFree 3) (hfree : Gᶜ.CliqueFree k) (v : α) (s t : Finset α) (hs : G.IsIndepSet s) (hns : ∀ x ∈ s, ¬ G.Adj v x) (ht : ∀ w, w ∈ t ↔ G.Adj v w ∧ ∀ x ∈ s, ¬ G.Adj w x) : s.card + t.card < k
- Source
- Neighborhood gluing approach for OP-926, https://arxiv.org/abs/2401.00392; elementary independent-set covering condition.
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- simple_graph_triangle_free_independent_neighborhood_matchingIn a finite triangle-free graph with no independent set of size k, if v has degree k − 1 and s is an independent set consisting of…
The proof, explained
The proof proceeds by contradiction: assuming |s| + |t| ≥ k, the disjoint union s ∪ t has size at least k. Since G is triangle-free, the neighborhood of v is independent, so its subset t is independent; together with s being independent and having no edges to t, the union s ∪ t is itself an independent set. A k-element subset of s ∪ t would then form an independent set of size k in G (equivalently, a k-clique in the complement graph Gᶜ), contradicting the assumption that no such set exists.
The sets s and t are disjoint.
Suppose for contradiction that some vertex x belongs to both s and t. Since x ∈ t, x must be a neighbor of v by the definition of t. But since x ∈ s, x is not a neighbor of v by hypothesis hns. This contradiction shows that s and t have no vertices in common.
uses
Finset.disjoint_left.mprclassical have hdisj : Disjoint s t := by apply Finset.disjoint_left.mpr intro x hxs hxt exact hns x hxs ((ht x).mp hxt).1
The set t is an independent set in G.
In any triangle-free graph, the neighborhood of every vertex forms an independent set (isIndepSet_neighborSet_of_triangleFree). Since every vertex in t is adjacent to v by the definition of t, t is a subset of the neighborhood of v, and therefore t is itself independent.
uses
isIndepSet_neighborSet_of_triangleFreehave htind : G.IsIndepSet t := by apply (G.isIndepSet_neighborSet_of_triangleFree htri v).mono intro x hx exact ((ht x).mp hx).1
The union s ∪ t is an independent set in G.
To show that no two distinct vertices x, y ∈ s ∪ t are adjacent, we consider which sets contain them. If both x, y ∈ s, they are non-adjacent because s is independent. If both x, y ∈ t, they are non-adjacent because t is independent. If one is in s and the other is in t, they are non-adjacent because every vertex in t is defined to have no neighbors in s. Thus s ∪ t is independent.
uses
Finset.coe_union,Set.mem_unionhave hst : G.IsIndepSet (s ∪ t : Finset α) := 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 hs hx hy hxy · exact fun hadj => ((ht y).mp hy).2 x hx hadj.symm · exact fun hadj => ((ht x).mp hx).2 y hy hadj · exact htind hx hy hxy
Assuming |s| + |t| ≥ k, the union s ∪ t has cardinality at least k.
We argue by contradiction and assume that |s| + |t| < k is false, so |s| + |t| ≥ k. Because s and t are disjoint, the cardinality of their union is |s ∪ t| = |s| + |t| by Finset.card_union_of_disjoint, which immediately gives k ≤ |s ∪ t|.
uses
Finset.card_union_of_disjointby_contra hn have hle : k ≤ (s ∪ t).card := by rw [Finset.card_union_of_disjoint hdisj] omega
A k-element subset of s ∪ t forms an independent set of size k in G, contradicting the hypothesis that G has no independent set of size k.
Because k ≤ |s ∪ t|, there exists a subset u ⊆ s ∪ t of size exactly k (Finset.exists_subset_card_eq). As a subset of the independent set s ∪ t, u is also an independent set in G. Being an independent set in G is equivalent to being a clique in the complement graph Gᶜ (SimpleGraph.isClique_compl), so u is a k-clique in Gᶜ (isNClique_iff). This contradicts hfree, the assumption that Gᶜ contains no k-cliques.
uses
Finset.exists_subset_card_eq,isNClique_iff,SimpleGraph.isClique_complobtain ⟨u, hus, huc⟩ := Finset.exists_subset_card_eq hle apply hfree u apply (Gᶜ.isNClique_iff).2 constructor · rw [SimpleGraph.isClique_compl] exact hst.mono (by exact_mod_cast hus) · exact huc
Finset.disjoint_left.mpr- Two finite sets are disjoint if no element of the first belongs to the second.
isIndepSet_neighborSet_of_triangleFree- In a triangle-free graph, the neighborhood of any vertex is an independent set.
Finset.coe_union- The coercion of the union of two finite sets to a set equals the union of their set coercions.
Set.mem_union- An element belongs to the union of two sets if and only if it belongs to the first or the second set.
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- A finite set whose cardinality is at least n contains a subset of cardinality exactly n.
isNClique_iff- A finite set of vertices is an n-clique in a graph if and only if it is a clique and has cardinality 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 original graph.
- The absence of independent sets of size k in G is expressed formally as the complement graph Gᶜ having no k-cliques (Gᶜ.CliqueFree k).
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_neighborhood_cover {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] (k : ℕ) (htri : G.CliqueFree 3) (hfree : Gᶜ.CliqueFree k) (v : α) (s t : Finset α) (hs : G.IsIndepSet s) (hns : ∀ x ∈ s, ¬ G.Adj v x) (ht : ∀ w, w ∈ t ↔ G.Adj v w ∧ ∀ x ∈ s, ¬ G.Adj w x) : s.card + t.card < k := by classical have hdisj : Disjoint s t := by apply Finset.disjoint_left.mpr intro x hxs hxt exact hns x hxs ((ht x).mp hxt).1 have htind : G.IsIndepSet t := by apply (G.isIndepSet_neighborSet_of_triangleFree htri v).mono intro x hx exact ((ht x).mp hx).1 have hst : G.IsIndepSet (s ∪ t : Finset α) := 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 hs hx hy hxy · exact fun hadj => ((ht y).mp hy).2 x hx hadj.symm · exact fun hadj => ((ht x).mp hx).2 y hy hadj · exact htind hx hy hxy by_contra hn have hle : k ≤ (s ∪ t).card := by rw [Finset.card_union_of_disjoint hdisj] omega obtain ⟨u, hus, huc⟩ := Finset.exists_subset_card_eq hle apply hfree u apply (Gᶜ.isNClique_iff).2 constructor · rw [SimpleGraph.isClique_compl] exact hst.mono (by exact_mod_cast hus) · exact huc