AFTD Auto-Formalizing Theoretical Domains

is_monochromatic_path_partition

def

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