simple_graph_ramsey_three_k_of_degree_ge
In any finite simple graph, if a vertex has degree at least k, then either the graph contains a triangle or it contains an independent set of size k (a k-clique of its complement).
Statement
theorem simple_graph_ramsey_three_k_of_degree_ge {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] {k : ℕ} (v : α) (hdeg : k ≤ G.degree v) : ¬ G.CliqueFree 3 ∨ ¬ Gᶜ.CliqueFree k
- Source
- step towards simple_graph_ramsey_three_ten_forty
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- simple_graph_ramsey_three_ten_forty_of_exists_degree_ge_tenAny simple graph on 40 vertices having a vertex of degree at least 10 contains a triangle or an independent set of size 10.
The proof, explained
The proof proceeds by case analysis on whether the graph G contains a triangle (a 3-clique). If it does, the first alternative holds immediately. If G is triangle-free, the neighborhood of any vertex v must be an independent set, since an edge between two neighbors would create a triangle with v. Because the degree of v is at least k, this neighborhood contains an independent set of size k, which is equivalently a k-clique in the complement graph Gᶜ, satisfying the second alternative.
Split into cases based on whether G is triangle-free.
We consider two cases: either the graph G contains no 3-clique (triangle-free), or it contains a 3-clique.
by_cases h3 : G.CliqueFree 3In the triangle-free case, suppose for contradiction that the complement graph Gᶜ has no k-clique.
We aim for the second alternative of the disjunction (that Gᶜ contains a k-clique), so we assume for contradiction that Gᶜ is k-clique-free.
· right intro hk
The neighborhood of v in G is an independent set.
Since G is triangle-free, no two neighbors of v can have an edge between them, because any such edge would form a triangle together with v.
uses
G.isIndepSet_neighborSet_of_triangleFreehave hindep : G.IsIndepSet (G.neighborSet v) := G.isIndepSet_neighborSet_of_triangleFree h3 vThe neighborhood of v has cardinality at least k.
The size of the neighborhood of v equals the degree of v, which is at least k by hypothesis.
uses
G.card_neighborFinset_eq_degreehave hcard : k ≤ (G.neighborFinset v).card := by rwa [G.card_neighborFinset_eq_degree]
There exists a subset s of the neighbors of v with size exactly k.
Because the finite neighborhood of v has at least k elements, we can extract a subset s of exactly k vertices.
uses
Finset.exists_subset_card_eqobtain ⟨s, hs_sub, hs_card⟩ := Finset.exists_subset_card_eq hcardThe subset s is an independent set in G.
Because s is a subset of the neighbors of v, and the neighborhood of v is independent in G, s is also an independent set.
uses
G.coe_neighborFinset,Finset.coe_subset.mprhave hs_indep : G.IsIndepSet (s : Set α) := by rw [← G.coe_neighborFinset] at hindep exact hindep.mono (Finset.coe_subset.mpr hs_sub)
A contradiction is reached: s is a k-clique in Gᶜ.
An independent set of size k in G corresponds to a k-clique in the complement graph Gᶜ. Exhibiting s as a k-clique in Gᶜ contradicts the assumption that Gᶜ is k-clique-free.
uses
SimpleGraph.isNClique_complhave hs_nclique : Gᶜ.IsNClique k s := by rw [SimpleGraph.isNClique_compl] exact ⟨hs_indep, hs_card⟩ exact hk s hs_nclique
If G is not triangle-free, the theorem holds immediately.
In the remaining case, G contains a triangle (is not 3-clique-free), directly fulfilling the first alternative of the disjunction.
· left exact h3
G.isIndepSet_neighborSet_of_triangleFree- In a triangle-free graph, the neighborhood of any vertex is an independent set.
G.card_neighborFinset_eq_degree- The number of vertices in the neighborhood of a vertex equals its degree.
Finset.exists_subset_card_eq- Any finite set of cardinality at least k contains a subset of cardinality k.
G.coe_neighborFinset- The coercion of the neighbor finset of a vertex to a set is the neighbor set.
Finset.coe_subset.mpr- If one finite set is a subset of another, their corresponding sets also satisfy the subset relation.
SimpleGraph.isNClique_compl- A set is an n-clique in the complement graph if and only if it is an independent set of size n 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
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.
/-- In any finite simple graph, if a vertex has degree at least k, then either the graph contains a triangle or an independent set of size k. -/theorem simple_graph_ramsey_three_k_of_degree_ge {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] {k : ℕ} (v : α) (hdeg : k ≤ G.degree v) : ¬ G.CliqueFree 3 ∨ ¬ Gᶜ.CliqueFree k := by by_cases h3 : G.CliqueFree 3 · right intro hk have hindep : G.IsIndepSet (G.neighborSet v) := G.isIndepSet_neighborSet_of_triangleFree h3 v have hcard : k ≤ (G.neighborFinset v).card := by rwa [G.card_neighborFinset_eq_degree] obtain ⟨s, hs_sub, hs_card⟩ := Finset.exists_subset_card_eq hcard have hs_indep : G.IsIndepSet (s : Set α) := by rw [← G.coe_neighborFinset] at hindep exact hindep.mono (Finset.coe_subset.mpr hs_sub) have hs_nclique : Gᶜ.IsNClique k s := by rw [SimpleGraph.isNClique_compl] exact ⟨hs_indep, hs_card⟩ exact hk s hs_nclique · left exact h3