is_monochromatic_path
A 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 exist a colour col : C, vertices u v : V, and a simple path p in the monochromatic subgraph mono_color_subgraph G c col from u to v such that s = p.support.toFinset.
Statement
def is_monochromatic_path {V C : Type*} [DecidableEq V] (G : SimpleGraph V) (c : G.edgeSet → C) (s : Finset V) : Prop
- Defined in
- arXiv:2611.06362 Section 1
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Built on 1
- mono_color_subgraphFor 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…
- Used by 3
- 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.
- is_monochromatic_path_partitionA collection P of finite vertex sets is a monochromatic path partition of a finite simple graph G with edge colouring c : G.edgeSet → C if…
Read back from the Lean
Given a type of vertices V with decidable equality, a type of colors C, a simple graph G on V, an edge coloring c : G.edgeSet → C, and a finite set of vertices s : Finset V:
is_monochromatic_path G c s asserts that there exist:
1. a color col : C,
2. vertices u, v : V, and
3. a walk p from u to v in the monochromatic subgraph mono_color_subgraph G c col,
such that p is a path (i.e., p.IsPath, meaning its vertex list p.support has no duplicates) and s is equal to the set of vertices visited by p (p.support.toFinset).
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
/-- Predicate asserting that a finite set of vertices spans a monochromatic path in an edge-coloured simple graph. -/ def is_monochromatic_path {V C : Type*} [DecidableEq V] (G : SimpleGraph V) (c : G.edgeSet → C) (s : Finset V) : Prop := ∃ (col : C) (u v : V) (p : (mono_color_subgraph G c col).Walk u v), p.IsPath ∧ s = p.support.toFinset