AFTD Auto-Formalizing Theoretical Domains

simple_graph_ramsey_three_ten_forty_outer_indep_lift

theoremverified

If I is an independent set of at least 9 vertices of a simple graph G, and v is a vertex outside I that is adjacent to no vertex of I, then G has an independent set of 10 vertices; equivalently the complement of G is not 10-clique-free.

Statement

theorem simple_graph_ramsey_three_ten_forty_outer_indep_lift {α : Type*} [DecidableEq α]
    (G : SimpleGraph α) {v : α} {I : Finset α}
    (hI : G.IsIndepSet (I : Set α)) (hv : v ∉ I)
    (hne : ∀ x ∈ I, ¬ G.Adj v x) (hcard : 9 ≤ I.card) :
    ¬ Gᶜ.CliqueFree 10
Source
step towards simple_graph_ramsey_three_ten_forty_of_max_degree_le_nine
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

To prove by contradiction that the complement graph Gᶜ is not 10-clique-free, we show that G contains an independent set of size 10. We augment the independent set I (which has at least 9 vertices) by the external vertex v to form J = I ∪ {v}, which remains independent because v has no neighbors in I. Since |J| ≥ 10, we can choose a 10-element subset t ⊆ J; this set t is a 10-element independent set in G, which corresponds to a 10-clique in Gᶜ and contradicts the assumption that Gᶜ is 10-clique-free.

  1. Assume for contradiction that the complement Gᶜ is 10-clique-free, and define J = I ∪ {v}.

    To establish the negation ¬ Gᶜ.CliqueFree 10, we introduce the contradiction hypothesis hcf that Gᶜ has no 10-clique. We then define the augmented vertex set J = I ∪ {v} by inserting the vertex v into I.

    lines 7–8

      intro hcf
      set J : Finset α := insert v I with hJ
  2. The augmented set J is an independent set in G.

    By SimpleGraph.isIndepSet_iff, an independent set is one whose vertices are pairwise non-adjacent. Expanding J = insert v I with Finset.coe_insert and Set.pairwise_insert reduces this to checking that I is pairwise non-adjacent (the hypothesis hI) and that v is non-adjacent to every vertex b ∈ I in both directions. For any b ∈ I (converted via Finset.mem_coe), ¬ G.Adj v b holds by the assumption hne, and symmetry of adjacency (G.adj_comm) gives ¬ G.Adj b v.

    lines 9–15

    uses SimpleGraph.isIndepSet_iff, Finset.coe_insert, Set.pairwise_insert, Finset.mem_coe, G.adj_comm

      have hJind : G.IsIndepSet (J : Set α) := by
        rw [SimpleGraph.isIndepSet_iff] at hI ⊢
        rw [hJ, Finset.coe_insert, Set.pairwise_insert]
        refine ⟨hI, ?_⟩
        intro b hb _
        rw [Finset.mem_coe] at hb
        exact ⟨hne b hb, fun h => hne b hb ((G.adj_comm b v).mp h)⟩
  3. The set J has cardinality at least 10.

    Because v ∉ I, Finset.card_insert_of_notMem gives |J| = |I| + 1. Since |I| ≥ 9 by hypothesis, the linear arithmetic solver omega deduces that |J| ≥ 10.

    lines 16–18

    uses Finset.card_insert_of_notMem

      have hJcard : 10 ≤ J.card := by
        rw [hJ, Finset.card_insert_of_notMem hv]
        omega
  4. There exists a subset t ⊆ J of size exactly 10.

    Because |J| ≥ 10, Finset.exists_subset_card_eq guarantees the existence of a 10-element subset t ⊆ J.

    line 19

    uses Finset.exists_subset_card_eq

      obtain ⟨t, htJ, htcard⟩ := Finset.exists_subset_card_eq hJcard
  5. The 10-element subset t is an independent set in G.

    Rewriting independence as pairwise non-adjacency via SimpleGraph.isIndepSet_iff, the property is inherited by subsets: any pair of distinct vertices in t is also in J. Using Finset.mem_coe.mp and Finset.mem_coe.mpr to mediate membership between Finset and Set, the pairwise non-adjacency of J restricts to t.

    lines 20–24

    uses SimpleGraph.isIndepSet_iff, Finset.mem_coe.mpr, Finset.mem_coe.mp

      have htind : G.IsIndepSet (t : Set α) := by
        rw [SimpleGraph.isIndepSet_iff] at hJind ⊢
        exact hJind.mono (by
          intro x hx
          exact Finset.mem_coe.mpr (htJ (Finset.mem_coe.mp hx)))
  6. The subset t is a 10-clique in Gᶜ, which contradicts the assumption that Gᶜ is 10-clique-free.

    By SimpleGraph.isNClique_compl and SimpleGraph.isNIndepSet_iff, an independent set of size 10 in G is precisely a 10-clique in Gᶜ. Having shown that t has 10 elements and is independent in G, t is a 10-clique in Gᶜ. Finally, SimpleGraph.IsNClique.not_cliqueFree shows that the presence of this 10-clique refutes the contradiction hypothesis hcf that Gᶜ is 10-clique-free.

    lines 25–28

    uses SimpleGraph.isNClique_compl, SimpleGraph.isNIndepSet_iff, SimpleGraph.IsNClique.not_cliqueFree

      have hncl : Gᶜ.IsNClique 10 t := by
        rw [SimpleGraph.isNClique_compl, SimpleGraph.isNIndepSet_iff]
        exact ⟨htind, htcard⟩
      exact (SimpleGraph.IsNClique.not_cliqueFree hncl) hcf
G.adj_comm
Adjacency in a simple graph G is symmetric: u is adjacent to v if and only if v is adjacent to u.
Finset.card_insert_of_notMem
Inserting an element into a finite set that does not contain it increases the cardinality of the set by 1.
Finset.coe_insert
The coercion of inserting an element into a finite set to a set equals inserting that element into the coerced set.
Finset.exists_subset_card_eq
A finite set of cardinality at least n contains a subset of cardinality exactly n.
Finset.mem_coe
An element belongs to the set coercion of a finite set if and only if it belongs to the finite set.
Finset.mem_coe.mp
If an element belongs to the set coercion of a finite set, then it belongs to the finite set.
Finset.mem_coe.mpr
If an element belongs to a finite set, then it belongs to the set coercion of the finite set.
SimpleGraph.isIndepSet_iff
A set of vertices is independent in a simple graph if and only if distinct vertices in the set are pairwise non-adjacent.
SimpleGraph.isNClique_compl
A finite set is an n-clique in the complement graph Gᶜ if and only if it is an n-independent set in G.
SimpleGraph.isNIndepSet_iff
A finite set is an n-independent set in G if and only if it is independent and has cardinality n.
SimpleGraph.IsNClique.not_cliqueFree
If a graph contains an n-clique, then it is not n-clique-free.
Set.pairwise_insert
A relation holds pairwise on insert a s if and only if it holds pairwise on s and holds between a and every other element of s in both directions.

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

/-- Lifting an outer independent set of size ≥ 9 by a non-adjacent vertex v gives an independent 10-set; hence the complement is not 10-clique-free. -/theorem simple_graph_ramsey_three_ten_forty_outer_indep_lift {α : Type*} [DecidableEq α]    (G : SimpleGraph α) {v : α} {I : Finset α}    (hI : G.IsIndepSet (I : Set α)) (hv : v ∉ I)    (hne : ∀ x ∈ I, ¬ G.Adj v x) (hcard : 9 ≤ I.card) :    ¬ Gᶜ.CliqueFree 10 := by  intro hcf  set J : Finset α := insert v I with hJ  have hJind : G.IsIndepSet (J : Set α) := by    rw [SimpleGraph.isIndepSet_iff] at hI ⊢    rw [hJ, Finset.coe_insert, Set.pairwise_insert]    refine ⟨hI, ?_⟩    intro b hb _    rw [Finset.mem_coe] at hb    exact ⟨hne b hb, fun h => hne b hb ((G.adj_comm b v).mp h)⟩  have hJcard : 10 ≤ J.card := by    rw [hJ, Finset.card_insert_of_notMem hv]    omega  obtain ⟨t, htJ, htcard⟩ := Finset.exists_subset_card_eq hJcard  have htind : G.IsIndepSet (t : Set α) := by    rw [SimpleGraph.isIndepSet_iff] at hJind ⊢    exact hJind.mono (by      intro x hx      exact Finset.mem_coe.mpr (htJ (Finset.mem_coe.mp hx)))  have hncl : Gᶜ.IsNClique 10 t := by    rw [SimpleGraph.isNClique_compl, SimpleGraph.isNIndepSet_iff]    exact ⟨htind, htcard⟩  exact (SimpleGraph.IsNClique.not_cliqueFree hncl) hcf
See it in the graphDiscuss this resultChallenge it