graph_125_noncolorable_complement_high_degree
If a 125-vertex graph has independence number at most three and its complement is not three-colorable, then it has a vertex of degree at least 46.
Statement
theorem graph_125_noncolorable_complement_high_degree
(G : SimpleGraph (Fin 125)) [DecidableRel G.Adj]
(hindep : G.IndepSetFree 4) (hcolor : ¬ Gᶜ.Colorable 3) :
∃ x, 46 ≤ G.degree x- Source
- Minimum-degree coloring reduction for OP-110.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- digraph_125_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 125 vertices with dominated arcs and a cycle in every in-neighborhood contains four…
The proof, explained
The proof proceeds by contradiction: assuming no vertex in G has degree at least 46, every vertex has degree at most 45. Consequently, every vertex in the complement graph Gᶜ has degree at least 124 - 45 = 79, so the minimum degree of Gᶜ is at least 79. Since G contains no 4-independent set, Gᶜ is K₄-free. By a theorem of Brandt on coloring clique-free graphs, any K₄-free graph on 125 vertices with minimum degree strictly greater than (5 · 125) / 8 = 78 must be 3-colorable, which contradicts the hypothesis that Gᶜ is not 3-colorable.
Assume for contradiction that no vertex has degree at least 46.
We enable classical logic and assume the negation of the existential goal, so that no vertex x satisfies 46 ≤ degree(x).
classical by_contra hnEvery vertex of G has degree at most 45.
For any vertex v, if its degree were not at most 45, it would be at least 46 by integer arithmetic (`omega`), contradicting the assumption that no vertex has degree at least 46.
have hd : ∀ v, G.degree v ≤ 45 := by intro v by_contra hv exact hn ⟨v, by omega⟩
The complement graph Gᶜ contains no 4-clique (it is K₄-free).
An independent set in G is a clique in Gᶜ. Since G has no independent set of size 4 (`hindep`), Gᶜ contains no clique of size 4.
have hf : Gᶜ.CliqueFree 4 := by simpa using hindep
The minimum degree of the complement graph Gᶜ is at least 79.
To bound the minimum degree from below, `Gᶜ.le_minDegree_of_forall_le_degree` reduces the goal to showing that every vertex has degree at least 79 in Gᶜ. For an arbitrary vertex v, `G.degree_compl` rewrites its degree in Gᶜ as |V| - 1 - degree(v), which simplifies to 125 - 1 - degree(v) using `Fintype.card_fin`. Since degree(v) ≤ 45, linear arithmetic (`omega`) confirms that 124 - degree(v) ≥ 79.
uses
Gᶜ.le_minDegree_of_forall_le_degree,G.degree_compl,Fintype.card_finhave hmin : 79 ≤ Gᶜ.minDegree := by apply Gᶜ.le_minDegree_of_forall_le_degree intro v rw [G.degree_compl] simp only [Fintype.card_fin] have hv := hd v omega
The minimum degree of Gᶜ strictly exceeds the threshold (3 · 3 - 4) · 125 / (3 · 3 - 1) = 78.
Arithmetic evaluation (`norm_num`) computes (3 · 3 - 4) · 125 / (3 · 3 - 1) = (5 · 125) / 8 = 78 under integer division. Since the minimum degree is at least 79, linear arithmetic (`omega`) establishes the strict inequality 78 < minDegree(Gᶜ).
have hth : (3*3-4)*Fintype.card (Fin 125)/(3*3-1) < Gᶜ.minDegree := by norm_num omega
A contradiction is reached, showing that G must have a vertex of degree at least 46.
Brandt's coloring theorem (`SimpleGraph.colorable_of_cliqueFree_lt_minDegree`) states that any graph without an (r + 1)-clique whose minimum degree exceeds (3r - 4)|V| / (3r - 1) is r-colorable. Applying this with r = 3 to Gᶜ yields that Gᶜ is 3-colorable, contradicting the hypothesis `hcolor` that Gᶜ is not 3-colorable.
uses
SimpleGraph.colorable_of_cliqueFree_lt_minDegreeexact hcolor (SimpleGraph.colorable_of_cliqueFree_lt_minDegree (G := Gᶜ) (r := 3) hf hth)
Gᶜ.le_minDegree_of_forall_le_degree- If every vertex of a finite graph has degree at least k, then the minimum degree of the graph is at least k.
G.degree_compl- The degree of a vertex v in the complement graph Gᶜ is |V| - 1 - degree(v).
Fintype.card_fin- The number of elements in the finite type Fin n is n.
SimpleGraph.colorable_of_cliqueFree_lt_minDegree- A graph with no (r + 1)-clique whose minimum degree strictly exceeds (3r - 4)|V| / (3r - 1) is r-colorable.
- The division in the threshold formula on line 19 is integer division on ℕ, so (5 * 125) / 8 evaluates to 78; thus the strict inequality threshold < minDegree is equivalent to minDegree ≥ 79.
- In line 11, `simpa` silently rewrites the definition: in Mathlib, an independent set in G is defined as a clique in the complement Gᶜ, making G.IndepSetFree 4 definitionally equivalent to Gᶜ.CliqueFree 4.
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 graph_125_noncolorable_complement_high_degree (G : SimpleGraph (Fin 125)) [DecidableRel G.Adj] (hindep : G.IndepSetFree 4) (hcolor : ¬ Gᶜ.Colorable 3) : ∃ x, 46 ≤ G.degree x := by classical by_contra hn have hd : ∀ v, G.degree v ≤ 45 := by intro v by_contra hv exact hn ⟨v, by omega⟩ have hf : Gᶜ.CliqueFree 4 := by simpa using hindep have hmin : 79 ≤ Gᶜ.minDegree := by apply Gᶜ.le_minDegree_of_forall_le_degree intro v rw [G.degree_compl] simp only [Fintype.card_fin] have hv := hd v omega have hth : (3*3-4)*Fintype.card (Fin 125)/(3*3-1) < Gᶜ.minDegree := by norm_num omega exact hcolor (SimpleGraph.colorable_of_cliqueFree_lt_minDegree (G := Gᶜ) (r := 3) hf hth)