AFTD Auto-Formalizing Theoretical Domains

mem_monochromatic_edges

theoremverified

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.

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

    lines 3–4

      classical
      unfold monochromatic_edges
  2. Membership 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.

    line 5

    uses Finset.mem_filter, SimpleGraph.mem_edgeFinset, SimpleGraph.mem_edgeSet, Sym2.lift_mk

      rw [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`.

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

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