mem_monochromatic_edges
For a finite type V, a simple graph G on V, a natural number k, a coloring c : V → Fin k, and vertices u and v, the unordered pair s(u, v) is in monochromatic_edges G c if and only if G.Adj u v and c u = c v.
Statement
theorem mem_monochromatic_edges {V : Type*} [Fintype V] (G : SimpleGraph V) {k : ℕ} (c : V → Fin k) (u v : V) : s(u, v) ∈ monochromatic_edges G c ↔ G.Adj u v ∧ c u = c v
- Source
- arXiv:2610.31489, Section 2
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- monochromatic_edgesGiven a finite type V, a simple graph G on V, a natural number k, and a coloring c : V → Fin k, monochromatic_edges G c is defined as the…
Read back from the Lean
For any finite type V, any simple graph G on V, any natural number k, any vertex coloring c : V → Fin k, and any vertices u, v : V, the unordered pair s(u, v) belongs to monochromatic_edges G c if and only if u and v are adjacent in G and have the same color under c (c u = c v).
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 lemma characterizes membership in the finset of monochromatic edges by unfolding its definition and rewriting each component. Monochromatic edges are defined by filtering the graph's edge finset with a lifted predicate testing color equality; rewriting decomposes this filter condition into edge membership (adjacency in G) and evaluates the lifted predicate directly on the endpoints u and v.
Unfolding the definition expresses monochromatic edges as a filtered finset of graph edges.
With classical decidability in scope, we unfold the definition of `monochromatic_edges`, which defines the set as the subfinset of `G.edgeFinset` filtered by the predicate checking whether the endpoints have the same color under `c`.
classical unfold monochromatic_edgesMembership of `s(u, v)` in the monochromatic edge set is equivalent to adjacency of `u` and `v` together with `c u = c v`.
Rewriting with `Finset.mem_filter` decomposes the membership condition into belonging to `G.edgeFinset` and satisfying the color-equality predicate. Next, `SimpleGraph.mem_edgeFinset` and `SimpleGraph.mem_edgeSet` rewrite membership in the edge finset to graph adjacency `G.Adj u v`. Finally, `Sym2.lift_mk` evaluates the lifted predicate on the unordered pair `s(u, v)` to `c u = c v`, leaving both sides of the bi-implication identical.
uses
Finset.mem_filter,SimpleGraph.mem_edgeFinset,SimpleGraph.mem_edgeSet,Sym2.lift_mkrw [Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Sym2.lift_mk]
Finset.mem_filter- An element belongs to a filtered finset `filter p s` if and only if it belongs to `s` and satisfies the predicate `p`.
SimpleGraph.mem_edgeFinset- An edge belongs to the edge finset `G.edgeFinset` of a simple graph if and only if it belongs to the graph's edge set `G.edgeSet`.
SimpleGraph.mem_edgeSet- An unordered pair `s(v, w)` belongs to the edge set of a graph `G` if and only if `v` and `w` are adjacent in `G`.
Sym2.lift_mk- Evaluating a symmetric function lifted to `Sym2` on an unordered pair `s(a, b)` yields the function applied directly to `a` and `b`.
- The tactic `rw` automatically closes reflexive goals of the form `P ↔ P`, so no separate reflexivity step is needed after the rewrites.
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.
/-- Characterization of membership in the set of monochromatic edges. -/theorem mem_monochromatic_edges {V : Type*} [Fintype V] (G : SimpleGraph V) {k : ℕ} (c : V → Fin k) (u v : V) : s(u, v) ∈ monochromatic_edges G c ↔ G.Adj u v ∧ c u = c v := by classical unfold monochromatic_edges rw [Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Sym2.lift_mk]