simple_graph_is_far_colorable_iff
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
- simple_graph_monochromatic_edgesGiven a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a vertex coloring c : V → Fin k, the…
- simple_graph_is_far_colorableA finite simple graph G on vertex type V is ε-far from being k-colorable if for every edge subset E' ⊆ E(G), whenever deleting E' from G…
- simple_graph_delete_monochromatic_edges_colorableFor any vertex coloring c : V → Fin k of a finite simple graph G on a type V with decidable equality and decidable adjacency, deleting the…
- simple_graph_exists_monochromatic_edges_subset_of_delete_edges_colorableFor any finite simple graph G on a type V with decidable equality and decidable adjacency, and any Finset E' of edges of Sym2 V such that…
- simple_graph_monochromatic_edges_subsetFor any vertex coloring c : V → Fin k of a finite simple graph G on a type V with decidable equality and decidable adjacency, the Finset…
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|².
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.
uses
simple_graph_monochromatic_edges_subset,simple_graph_delete_monochromatic_edges_colorableconstructor · 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
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'|.
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.
- The cardinality inequality in Step 2 is cast from ℕ to ℝ using `exact_mod_cast` before applying transitivity with the real-valued lower bound ε * |V|².
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.
/-- 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