AFTD Auto-Formalizing Theoretical Domains

simple_graph_monochromatic_edges

def

Given 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 Finset simple_graph_monochromatic_edges G c consists of all edges e ∈ G.edgeFinset such that (Sym2.map c e).IsDiag.

Statement

def simple_graph_monochromatic_edges {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (c : V → Fin k) : Finset (Sym2 V)
Defined in
combinatorics/2610-31489-near-optimal-bounds-for-testing-k-colorability.md:128
Verified
25 Oct 2026
Axioms
none listed
Used by 4

Read back from the Lean

Given a finite type $V$ with decidable equality, a simple graph $G$ on $V$ with decidable adjacency, a natural number $k$, and a coloring function $c : V \to \text{Fin } k$, simple_graph_monochromatic_edges is defined as the finite set of edges $e \in G.\text{edgeFinset}$ such that the image of $e$ under $c$ in $\text{Sym2}(\text{Fin } k)$ is diagonal (i.e., both endpoints of $e$ are assigned the same color by $c$).

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

Lean source view module on GitHub

/-- The Finset of monochromatic edges of a finite simple graph under a vertex coloring c : V → Fin k. -/
def simple_graph_monochromatic_edges {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (c : V → Fin k) : Finset (Sym2 V) := G.edgeFinset.filter (fun e => (Sym2.map c e).IsDiag)
See it in the graphDiscuss this resultChallenge it