AFTD Auto-Formalizing Theoretical Domains

simple_graph_delete_monochromatic_edges_colorable

theoremverified

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.

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

    line 5

    uses SimpleGraph.Coloring.mk

      refine ⟨SimpleGraph.Coloring.mk c ?_⟩
  2. 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.

    lines 6–8

    uses SimpleGraph.deleteEdges_adj

      intro v w hvw
      rw [SimpleGraph.deleteEdges_adj] at hvw
      rcases hvw with ⟨hadj, hnotmem⟩
  3. 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.

    lines 9–10

      intro heq
      apply hnotmem
  4. 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.

    lines 11–14

    uses simple_graph_monochromatic_edges, Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet

      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]
  5. 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.

    lines 15–16

    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

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