simple_graph_monochromatic_edges_subset
For 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 of monochromatic edges simple_graph_monochromatic_edges G c is a subset of G.edgeFinset.
Statement
theorem simple_graph_monochromatic_edges_subset {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (c : V → Fin k) : simple_graph_monochromatic_edges G c ⊆ G.edgeFinset
- 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 any finite type $V$ with decidable equality, any simple graph $G$ on $V$ with decidable adjacency, any natural number $k$, and any vertex coloring $c : V \to \text{Fin } k$, the finset of monochromatic edges of $G$ under $c$ is a subset of the edge finset of $G$ (G.edgeFinset).
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
By definition, the set of monochromatic edges `simple_graph_monochromatic_edges G c` is obtained by filtering `G.edgeFinset` to retain only edges whose endpoints are assigned the same color by `c`. The claim then holds immediately from `Finset.filter_subset`, which asserts that filtering any finite set yields a subset of the original set.
The set of monochromatic edges is a subset of the graph's edge set.
By definition, `simple_graph_monochromatic_edges G c` is the sub-finset of `G.edgeFinset` consisting of edges whose endpoints receive the same color under `c`. Applying the lemma `Finset.filter_subset` establishes directly that filtering `G.edgeFinset` yields a subset of `G.edgeFinset`.
uses
Finset.filter_subsetFinset.filter_subset _ _
Finset.filter_subset- Filtering a finite set `s` by any decidable predicate `p` yields a subset of `s`.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- The Finset of monochromatic edges under any vertex coloring c of G is a subset of G.edgeFinset. -/theorem simple_graph_monochromatic_edges_subset {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] {k : ℕ} (c : V → Fin k) : simple_graph_monochromatic_edges G c ⊆ G.edgeFinset := Finset.filter_subset _ _