AFTD Auto-Formalizing Theoretical Domains

is_monochromatic_path_singleton

theoremverified

For 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 vertex v : V, the singleton set {v} is a monochromatic path in G with respect to c.

Statement

lemma is_monochromatic_path_singleton {V C : Type*} [DecidableEq V] [Nonempty C] (G : SimpleGraph V)
    (c : G.edgeSet → C) (v : V) :
    is_monochromatic_path G c {v}
Source
arXiv:2611.06362 Section 1
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • 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…

Read back from the Lean

For any types V and C where V has decidable equality and C is nonempty, any simple graph G on V, any edge coloring c : G.edgeSet → C, and any vertex v : V, the singleton vertex set {v} is a monochromatic path in G with respect to c (that is, there exists a color col : C, vertices x, y : V, and a path p from x to y in the subgraph of G consisting of edges of color col, whose vertex set is {v}).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

By definition, a set of vertices forms a monochromatic path if it is the vertex set of some path whose edges all share the same color. For a singleton {v}, we choose an arbitrary color from the nonempty color set and consider the trivial zero-edge walk at v. This trivial walk is automatically a path and has vertex set {v}, satisfying the definition vacuously since it contains no edges.

  1. To show {v} is a monochromatic path, it suffices to verify that the trivial walk at v is a path and that its vertex set is {v}.

    By definition, a set of vertices is a monochromatic path if there exists a color, two endpoints, and a path between them in the corresponding monochromatic subgraph whose vertices comprise the set. Since the color type C is nonempty, we select an arbitrary color via Classical.arbitrary C. Setting both endpoints to v, we supply the trivial walk of length zero at v (SimpleGraph.Walk.nil). This leaves two goals: showing that this walk is a path, and showing that its vertex set is {v}.

    lines 5–6

    uses Classical.arbitrary, SimpleGraph.Walk.nil

      classical
      refine ⟨Classical.arbitrary C, v, v, SimpleGraph.Walk.nil, ?_, ?_⟩
  2. The trivial walk at v is a path.

    A walk of length zero contains only the single vertex v and no edges, so it has no repeated vertices; this is stated directly by SimpleGraph.Walk.IsPath.nil.

    line 7

    uses SimpleGraph.Walk.IsPath.nil

      · exact SimpleGraph.Walk.IsPath.nil
  3. The vertex set of the trivial walk at v is {v}. automation

    The vertex list (support) of the trivial walk at v is the singleton list [v], whose conversion to a finite set is {v}. Simplification evaluates this definition and closes the equality {v} = {v}.

    line 8

      · simp
Classical.arbitrary
Given a proof that a type α is nonempty, produces an arbitrary element of α.
SimpleGraph.Walk.nil
The trivial walk of length zero starting and ending at a given vertex u in a graph G.
SimpleGraph.Walk.IsPath.nil
The trivial walk of length zero at any vertex u is a path (it has no repeated vertices).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- A single vertex is the vertex set of a trivial monochromatic path. -/lemma is_monochromatic_path_singleton {V C : Type*} [DecidableEq V] [Nonempty C] (G : SimpleGraph V)    (c : G.edgeSet → C) (v : V) :    is_monochromatic_path G c {v} := by  classical  refine ⟨Classical.arbitrary C, v, v, SimpleGraph.Walk.nil, ?_, ?_⟩  · exact SimpleGraph.Walk.IsPath.nil  · simp
See it in the graphDiscuss this resultChallenge it