AFTD Auto-Formalizing Theoretical Domains

is_monochromatic_path

def

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