AFTD Auto-Formalizing Theoretical Domains

mono_color_subgraph

def

For a simple graph G and an edge colouring c with colours in C, the monochromatic subgraph mono_color_subgraph G c col is the spanning subgraph of G whose edges are all edges of G assigned colour col.

Statement

def mono_color_subgraph {V C : Type*} (G : SimpleGraph V) (c : G.edgeSet → C) (col : C) : SimpleGraph V
Defined in
arXiv:2610.29813
Verified
22 Oct 2026
Axioms
none listed
Used by 5
  • is_monochromatic_path_singletonFor any types V and C with decidable equality on V and nonempty C, any simple graph G on V, any edge colouring c : G.edgeSet → C, and any…
  • not_is_monochromatic_path_emptyThe empty set of vertices is not a monochromatic path in any edge-coloured simple graph G under any edge colouring c : G.edgeSet → C.
  • bipartite_ramsey_propertyFor a simple graph H and natural numbers r and N, bipartite_ramsey_property H r N holds if every r-edge-colouring of the complete…
  • mono_color_subgraph_leThe monochromatic subgraph of G in colour col is a subgraph of G.
  • is_monochromatic_pathA finite set of vertices s in a simple graph G with edge colouring c : G.edgeSet → C is the vertex set of a monochromatic path if there…

Read back from the Lean

Given types V and C, a simple graph G on V, an edge-coloring function c : G.edgeSet → C, and a color col : C, mono_color_subgraph G c col is the simple graph on the vertex type V whose edge set is formed via SimpleGraph.fromEdgeSet from the set of edges e : Sym2 V such that e ∈ G.edgeSet and c ⟨e, h⟩ = col. That is, it is the spanning subgraph of G keeping only the edges colored col.

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 monochromatic subgraph of G in colour col under edge colouring c. -/
def mono_color_subgraph {V C : Type*} (G : SimpleGraph V) (c : G.edgeSet → C) (col : C) : SimpleGraph V :=
  SimpleGraph.fromEdgeSet {e | ∃ h : e ∈ G.edgeSet, c ⟨e, h⟩ = col}
See it in the graphDiscuss this resultChallenge it