is_monochromatic_path_partition
A 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 the sets in P are pairwise disjoint, their union is Finset.univ, and every set in P is a monochromatic path in G under c.
Statement
def is_monochromatic_path_partition {V C : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) (c : G.edgeSet → C) (P : Finset (Finset V)) : Prop
- Defined in
- arXiv:2611.06362 Section 1
- Verified
- 05 Nov 2026
- Axioms
- none listed
- Built on 1
- 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
For a finite vertex type V with decidable equality, a color type C, a simple graph G on V, an edge-coloring c : G.edgeSet → C, and a family P of finite subsets of V (P : Finset (Finset V)), is_monochromatic_path_partition G c P asserts that:
1. The subsets in P are pairwise disjoint (i.e., for any distinct s₁, s₂ ∈ P, s₁ ∩ s₂ = ∅).
2. The union of all subsets in P is the entire vertex set V (Finset.univ).
3. For every s ∈ P, s is the vertex set of a monochromatic path under c, meaning there exist a color col : C, vertices u, v : V, and a walk p from u to v in the subgraph of G spanned by edges of color col, such that p is a path (its vertex sequence contains no repeated vertices) and s equals the set of vertices visited by p.
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 family of vertex subsets partitions the vertex set into vertex-disjoint monochromatic paths. -/ def is_monochromatic_path_partition {V C : Type*} [DecidableEq V] [Fintype V] (G : SimpleGraph V) (c : G.edgeSet → C) (P : Finset (Finset V)) : Prop := (P : Set (Finset V)).PairwiseDisjoint id ∧ P.biUnion id = Finset.univ ∧ ∀ s ∈ P, is_monochromatic_path G c s