not_is_monochromatic_path_empty
The empty set of vertices is not a monochromatic path in any edge-coloured simple graph G under any edge colouring c : G.edgeSet → C.
Statement
lemma not_is_monochromatic_path_empty {V C : Type*} [DecidableEq V] (G : SimpleGraph V) (c : G.edgeSet → C) : ¬ is_monochromatic_path G c ∅
- 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$ (with decidable equality on $V$), for every simple graph $G$ on $V$, and for every edge-coloring $c : G.edgeSet \to C$, the empty set $\emptyset$ is not a monochromatic path in $G$ under $c$. That is, there does not exist a color $\text{col} : C$, vertices $u, v : V$, and a walk $p$ from $u$ to $v$ in the monochromatic subgraph of $G$ with color $\text{col}$ such that $p$ is a simple path and the vertex support of $p$ (converted to a Finset) is empty.
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
The proof proceeds by contradiction: suppose the empty set of vertices is a monochromatic path in G. By definition, such a path corresponds to a walk p starting at some vertex u whose vertex set is empty. However, every walk contains its starting vertex in its support, implying that u belongs to the empty set, which is impossible.
Assume for contradiction that ∅ is a monochromatic path, giving a walk p from vertex u to v whose vertex set is empty.
We assume the negation of the goal and unpack the existential definition of `is_monochromatic_path G c ∅`. This introduces a color `col`, vertices `u` and `v`, and a walk `p` between them such that ∅ equals `p.support.toFinset` (named `hsp`).
rintro ⟨col, u, v, p, hp, hsp⟩
The starting vertex u belongs to the vertex sequence (support) of p.
By `p.start_mem_support`, the starting vertex of any walk is always an element of its support.
uses
p.start_mem_supporthave h_mem : u ∈ p.support := p.start_mem_supportThe starting vertex u belongs to the empty set ∅.
Rewriting with the assumption `hsp` that ∅ = `p.support.toFinset`, the goal becomes `u ∈ p.support.toFinset`. This holds by `List.mem_toFinset.mpr` because `u ∈ p.support`.
uses
List.mem_toFinset.mprhave h : u ∈ (∅ : Finset V) := by rw [hsp] exact List.mem_toFinset.mpr h_mem
A contradiction is derived, completing the proof. automation
Simplifying the hypothesis `h : u ∈ ∅` produces `False` because the empty set has no elements, which immediately closes the refutation.
simp at h
p.start_mem_support- The starting vertex of a walk belongs to its support (the list of vertices it visits).
List.mem_toFinset.mpr- If an element belongs to a list, it belongs to the finite set formed by that list.
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.
/-- The empty set cannot be the vertex set of a monochromatic path. -/lemma not_is_monochromatic_path_empty {V C : Type*} [DecidableEq V] (G : SimpleGraph V) (c : G.edgeSet → C) : ¬ is_monochromatic_path G c ∅ := by rintro ⟨col, u, v, p, hp, hsp⟩ have h_mem : u ∈ p.support := p.start_mem_support have h : u ∈ (∅ : Finset V) := by rw [hsp] exact List.mem_toFinset.mpr h_mem simp at h