is_monochromatic_path_singleton
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.
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}.
uses
Classical.arbitrary,SimpleGraph.Walk.nilclassical refine ⟨Classical.arbitrary C, v, v, SimpleGraph.Walk.nil, ?_, ?_⟩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.
uses
SimpleGraph.Walk.IsPath.nil· exact SimpleGraph.Walk.IsPath.nilThe 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}.
· 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).
- The definition of `is_monochromatic_path` requires choosing a specific color `col : C` even though a zero-edge path contains no edges; the proof therefore uses `[Nonempty C]` and classical choice to provide a dummy color.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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