AFTD Auto-Formalizing Theoretical Domains

not_is_monochromatic_path_empty

theoremverified

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.

  1. 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`).

    line 5

      rintro ⟨col, u, v, p, hp, hsp⟩
  2. 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.

    line 6

    uses p.start_mem_support

      have h_mem : u ∈ p.support := p.start_mem_support
  3. The 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`.

    lines 7–9

    uses List.mem_toFinset.mpr

      have h : u ∈ (∅ : Finset V) := by
        rw [hsp]
        exact List.mem_toFinset.mpr h_mem
  4. 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.

    line 10

      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

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