AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_far_colorable_iff

theoremverifiedformalization

A finite simple graph G on a type V with decidable equality and decidable adjacency is ε-far from being k-colorable if and only if every vertex coloring c : V → Fin k satisfies ε * (Fintype.card V : ℝ) ^ 2 ≤ ((simple_graph_monochromatic_edges G c).card : ℝ).

Statement

theorem simple_graph_is_far_colorable_iff {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (ε : ℝ) :
    simple_graph_is_far_colorable G k ε ↔
      ∀ c : V → Fin k, ε * (Fintype.card V : ℝ) ^ 2 ≤ ((simple_graph_monochromatic_edges G c).card : ℝ)
Formalizes
combinatorics/2610-31489-near-optimal-bounds-for-testing-k-colorability.md:152
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5

Read back from the Lean

For any finite type $V$ with decidable equality, any simple graph $G$ on $V$ with decidable adjacency, any natural number $k$, and any real number $\varepsilon$: The graph $G$ is $\varepsilon$-far from being $k$-colorable (simple_graph_is_far_colorable G k ε) if and only if for every coloring $c : V \to \mathrm{Fin}\ k$, the number of monochromatic edges of $G$ under $c$ is at least $\varepsilon \cdot |V|^2$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The equivalence is proved in two directions. For the forward direction, deleting the monochromatic edges of any k-coloring yields a k-colorable subgraph, so by assumption their count must be at least ε |V|². For the reverse direction, given any edge set whose deletion leaves a k-colorable subgraph, any proper k-coloring of that subgraph has all its original monochromatic edges contained within the deleted set, so the assumption bounds the size of the deleted set from below by ε |V|².

  1. If G is ε-far from k-colorable, then every k-coloring of G has at least ε |V|² monochromatic edges.

    We split the equivalence into two implications. For the forward direction, assume that G is ε-far from k-colorable and let c : V → Fin k be an arbitrary vertex coloring. The monochromatic edges of c form a subset of the edges of G (`simple_graph_monochromatic_edges_subset`), and deleting them removes all monochromatic edges, rendering the graph k-colorable (`simple_graph_delete_monochromatic_edges_colorable`). By the definition of being ε-far from k-colorable, any such edge set must have size at least ε |V|², so c has at least ε |V|² monochromatic edges.

    lines 6–12

    uses simple_graph_monochromatic_edges_subset, simple_graph_delete_monochromatic_edges_colorable

      constructor
      · intro h c
        have hsub : simple_graph_monochromatic_edges G c ⊆ G.edgeFinset :=
          simple_graph_monochromatic_edges_subset G c
        have hcol : (G.deleteEdges (simple_graph_monochromatic_edges G c : Set (Sym2 V))).Colorable k :=
          simple_graph_delete_monochromatic_edges_colorable G c
        exact h (simple_graph_monochromatic_edges G c) hsub hcol
  2. Conversely, if every k-coloring of G has at least ε |V|² monochromatic edges, then G is ε-far from k-colorable.

    Assume every coloring has at least ε |V|² monochromatic edges. To show that G is ε-far from k-colorable, let E' ⊆ E(G) be any set of edges whose deletion leaves a k-colorable graph. Any proper k-coloring of G \ E' gives a coloring c : V → Fin k whose monochromatic edges in G are contained in E' (`simple_graph_exists_monochromatic_edges_subset_of_delete_edges_colorable`). Consequently, the number of monochromatic edges of c is at most |E'| (`Finset.card_le_card`). Applying transitivity of inequality (`le_trans`) to the assumption ε |V|² ≤ |simple_graph_monochromatic_edges G c| and this upper bound yields ε |V|² ≤ |E'|.

    lines 13–17

    uses simple_graph_exists_monochromatic_edges_subset_of_delete_edges_colorable, Finset.card_le_card, le_trans

      · intro h E' hsub hcol
        rcases simple_graph_exists_monochromatic_edges_subset_of_delete_edges_colorable G hcol with ⟨c, hc⟩
        have hle : ((simple_graph_monochromatic_edges G c).card : ℝ) ≤ (E'.card : ℝ) := by
          exact_mod_cast Finset.card_le_card hc
        exact le_trans (h c) hle
simple_graph_monochromatic_edges_subset
The monochromatic edges of any vertex coloring form a subset of the graph's edge set.
simple_graph_delete_monochromatic_edges_colorable
Deleting all monochromatic edges of a coloring c : V → Fin k from G yields a k-colorable graph.
simple_graph_exists_monochromatic_edges_subset_of_delete_edges_colorable
If deleting an edge set E' leaves a k-colorable graph, there exists a coloring c : V → Fin k whose monochromatic edges are all contained in E'.
Finset.card_le_card
If a finite set s is a subset of a finite set t, then |s| ≤ |t|.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.

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

/-- A graph G is ε-far from being k-colorable if and only if every vertex coloring c : V → Fin k has at least ε |V|² monochromatic edges. -/theorem simple_graph_is_far_colorable_iff {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ) (ε : ℝ) :    simple_graph_is_far_colorable G k ε ↔      ∀ c : V → Fin k, ε * (Fintype.card V : ℝ) ^ 2 ≤ ((simple_graph_monochromatic_edges G c).card : ℝ) := by  constructor  · intro h c    have hsub : simple_graph_monochromatic_edges G c ⊆ G.edgeFinset :=      simple_graph_monochromatic_edges_subset G c    have hcol : (G.deleteEdges (simple_graph_monochromatic_edges G c : Set (Sym2 V))).Colorable k :=      simple_graph_delete_monochromatic_edges_colorable G c    exact h (simple_graph_monochromatic_edges G c) hsub hcol  · intro h E' hsub hcol    rcases simple_graph_exists_monochromatic_edges_subset_of_delete_edges_colorable G hcol with ⟨c, hc⟩    have hle : ((simple_graph_monochromatic_edges G c).card : ℝ) ≤ (E'.card : ℝ) := by      exact_mod_cast Finset.card_le_card hc    exact le_trans (h c) hle
See it in the graphDiscuss this resultChallenge it