simple_graph_ramsey_three_ten_forty_outer_indep_lift
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.
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.
intro hcf set J : Finset α := insert v I with hJ
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.
uses
SimpleGraph.isIndepSet_iff,Finset.coe_insert,Set.pairwise_insert,Finset.mem_coe,G.adj_commhave 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)⟩
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.
uses
Finset.card_insert_of_notMemhave hJcard : 10 ≤ J.card := by rw [hJ, Finset.card_insert_of_notMem hv] omega
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.
uses
Finset.exists_subset_card_eqobtain ⟨t, htJ, htcard⟩ := Finset.exists_subset_card_eq hJcardThe 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.
uses
SimpleGraph.isIndepSet_iff,Finset.mem_coe.mpr,Finset.mem_coe.mphave 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)))
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.
uses
SimpleGraph.isNClique_compl,SimpleGraph.isNIndepSet_iff,SimpleGraph.IsNClique.not_cliqueFreehave 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.
- In Lean, graph-theoretic independence is formulated on general sets (`Set α`), while finite subsets are of type `Finset α`. As a result, several steps use coercion lemmas (`Finset.mem_coe`, `Finset.coe_insert`) to bridge between finite set operations and pairwise relations on 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.
/-- 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