AFTD Auto-Formalizing Theoretical Domains

graph_125_noncolorable_complement_high_degree

theoremverified

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

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.

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

    lines 5–6

      classical
      by_contra hn
  2. Every 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.

    lines 7–10

      have hd : ∀ v, G.degree v ≤ 45 := by
        intro v
        by_contra hv
        exact hn ⟨v, by omega⟩
  3. 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.

    line 11

      have hf : Gᶜ.CliqueFree 4 := by simpa using hindep
  4. 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.

    lines 12–18

    uses Gᶜ.le_minDegree_of_forall_le_degree, G.degree_compl, Fintype.card_fin

      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
  5. 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ᶜ).

    lines 19–21

      have hth : (3*3-4)*Fintype.card (Fin 125)/(3*3-1) < Gᶜ.minDegree := by
        norm_num
        omega
  6. 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.

    line 22

    uses SimpleGraph.colorable_of_cliqueFree_lt_minDegree

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

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