AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_free_independent_neighborhood_cover

theoremverified

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

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.

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

    lines 7–11

    uses Finset.disjoint_left.mpr

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

    lines 12–15

    uses isIndepSet_neighborSet_of_triangleFree

      have htind : G.IsIndepSet t := by
        apply (G.isIndepSet_neighborSet_of_triangleFree htri v).mono
        intro x hx
        exact ((ht x).mp hx).1
  3. 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.

    lines 16–23

    uses Finset.coe_union, Set.mem_union

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

    lines 24–27

    uses Finset.card_union_of_disjoint

      by_contra hn
      have hle : k ≤ (s ∪ t).card := by
        rw [Finset.card_union_of_disjoint hdisj]
        omega
  5. 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.

    lines 28–34

    uses Finset.exists_subset_card_eq, isNClique_iff, SimpleGraph.isClique_compl

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

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