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}