AFTD Auto-Formalizing Theoretical Domains

simple_graph_monochromatic_edges_subset

theoremverified

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.

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

    line 5

    uses Finset.filter_subset

      Finset.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 _ _
See it in the graphDiscuss this resultChallenge it