simple_graph_monochromatic_edges
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
- 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_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…
- 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_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
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)