simple_graph_delete_monochromatic_edges_colorable
For 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 Finset of monochromatic edges simple_graph_monochromatic_edges G c from G leaves a k-colorable graph.
Statement
theorem simple_graph_delete_monochromatic_edges_colorable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (c : V → Fin k) : (G.deleteEdges (simple_graph_monochromatic_edges G c : Set (Sym2 V))).Colorable k
- Source
- combinatorics/2610-31489-near-optimal-bounds-for-testing-k-colorability.md:160
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 1
- simple_graph_is_far_colorable_iffA 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…
Read back from the Lean
For every finite type $V$ with decidable equality, every simple graph $G$ on $V$ with decidable adjacency, every natural number $k$, and every function $c : V \to \mathrm{Fin}\ k$, the simple graph obtained from $G$ by deleting all monochromatic edges under $c$ (that is, all edges of $G$ whose endpoints receive the same value under $c$) is $k$-colorable (i.e., admits a proper $k$-coloring).
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 theorem establishes that deleting all monochromatic edges with respect to a vertex coloring c : V → Fin k leaves a k-colorable graph. The proof uses c itself as the proper k-coloring of the remaining graph. If any edge in the remaining graph had both endpoints of the same color under c, it would be a monochromatic edge and therefore would have been deleted, a contradiction.
The vertex coloring c is a proper k-coloring of the edge-deleted graph, provided that any two adjacent vertices in this graph receive different colors under c.
To prove that the graph remaining after deleting monochromatic edges is k-colorable, we provide c itself as the witness coloring via SimpleGraph.Coloring.mk. This reduces the problem to showing that whenever two vertices v and w are adjacent in the edge-deleted graph, c(v) ≠ c(w).
uses
SimpleGraph.Coloring.mkrefine ⟨SimpleGraph.Coloring.mk c ?_⟩If v and w are adjacent in the edge-deleted graph, then they are adjacent in G and the edge {v, w} is not in the set of monochromatic edges.
We introduce two adjacent vertices v and w in the edge-deleted graph. By SimpleGraph.deleteEdges_adj, adjacency in G.deleteEdges s means that v and w were adjacent in G and the undirected edge s(v, w) was not in the set s of deleted monochromatic edges.
uses
SimpleGraph.deleteEdges_adjintro v w hvw rw [SimpleGraph.deleteEdges_adj] at hvw rcases hvw with ⟨hadj, hnotmem⟩
To show c(v) ≠ c(w), it suffices to show that {v, w} is a monochromatic edge in G.
We assume for contradiction that c(v) = c(w). Under this assumption, it suffices to prove that s(v, w) is a monochromatic edge of G, which contradicts the fact established in the previous step that s(v, w) was not deleted.
intro heq apply hnotmem
The edge {v, w} is an edge of the original graph G.
Unfolding the definition of monochromatic edges and rewriting with Finset.mem_filter, an edge belongs to simple_graph_monochromatic_edges G c if it belongs to G.edgeFinset and its endpoints have the same color under c. We split this conjunction into two goals. The first goal requires s(v, w) to be in G.edgeFinset, which is equivalent to G.Adj v w by SimpleGraph.mem_edgeFinset and SimpleGraph.mem_edgeSet, and this holds by assumption.
uses
simple_graph_monochromatic_edges,Finset.mem_filter,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSetchange s(v, w) ∈ simple_graph_monochromatic_edges G c rw [simple_graph_monochromatic_edges, Finset.mem_filter] refine ⟨?_, ?_⟩ · rwa [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet]
The edge {v, w} is monochromatic under c, completing the contradiction.
The second goal requires the image of s(v, w) under c to be diagonal. By Sym2.map_mk, this image is s(c(v), c(w)), and by Sym2.mk_isDiag_iff, an unordered pair is diagonal if and only if its two entries are equal. This reduces the goal to c(v) = c(w), which is our assumed hypothesis.
uses
Sym2.map_mk,Sym2.mk_isDiag_iff· rw [Sym2.map_mk, Sym2.mk_isDiag_iff] exact heq
SimpleGraph.Coloring.mk- A coloring of a graph is constructed from a vertex coloring function by verifying that adjacent vertices are assigned distinct colors.
SimpleGraph.deleteEdges_adj- Two vertices are adjacent in an edge-deleted graph if and only if they are adjacent in the original graph and the edge between them was not deleted.
simple_graph_monochromatic_edges- The set of monochromatic edges under a vertex coloring c is the collection of graph edges whose two endpoints are assigned the same color.
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the set and satisfies the filtering predicate.
SimpleGraph.mem_edgeFinset- An edge belongs to the finite edge set of a graph if and only if it belongs to its edge set.
SimpleGraph.mem_edgeSet- An unordered pair of vertices belongs to the edge set of a graph if and only if the two vertices are adjacent in the graph.
Sym2.map_mk- Mapping a function over an unordered pair applies the function to both endpoints: Sym2.map f s(a, b) = s(f a, f b).
Sym2.mk_isDiag_iff- An unordered pair s(x, y) is diagonal (consists of identical elements) if and only if x = y.
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.
/-- Deleting all monochromatic edges under a vertex coloring c makes the remaining graph k-colorable. -/theorem simple_graph_delete_monochromatic_edges_colorable {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (c : V → Fin k) : (G.deleteEdges (simple_graph_monochromatic_edges G c : Set (Sym2 V))).Colorable k := by refine ⟨SimpleGraph.Coloring.mk c ?_⟩ intro v w hvw rw [SimpleGraph.deleteEdges_adj] at hvw rcases hvw with ⟨hadj, hnotmem⟩ intro heq apply hnotmem change s(v, w) ∈ simple_graph_monochromatic_edges G c rw [simple_graph_monochromatic_edges, Finset.mem_filter] refine ⟨?_, ?_⟩ · rwa [SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet] · rw [Sym2.map_mk, Sym2.mk_isDiag_iff] exact heq