AFTD Auto-Formalizing Theoretical Domains

is_spanning_path_graph_pathGraph_three

theoremverified

The path graph on three vertices is a spanning path.

Statement

theorem is_spanning_path_graph_pathGraph_three : is_spanning_path_graph (SimpleGraph.pathGraph 3)
Source
sanity check of is_spanning_path_graph
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_spanning_path_graphA graph on n vertices is a spanning path if its vertices can be ordered so that exactly consecutive vertices are adjacent.

The proof, explained

To show that the path graph on three vertices is a spanning path graph, we provide the identity permutation on its vertices as the witness. Under the identity permutation, the required condition is that two vertices are adjacent if and only if their indices differ by one, which is the definition of adjacency in a path graph.

  1. The identity permutation witnesses that the path graph on three vertices is a spanning path.

    We instantiate the existential quantifier in the definition of a spanning path graph with the identity permutation on $\operatorname{Fin} 3$. For any vertices $a$ and $b$, the identity permutation satisfies $1(a) = a$ and $1(b) = b$, so the condition reduces to the definition of adjacency in the path graph given by `SimpleGraph.pathGraph_adj`, closing the equivalence.

    line 2

    uses SimpleGraph.pathGraph_adj

      ⟨1, fun a b => by simp [SimpleGraph.pathGraph_adj]⟩
SimpleGraph.pathGraph_adj
In a path graph on $n$ vertices, two vertices $u$ and $v$ are adjacent if and only if their integer values differ by $1$ ($u + 1 = v$ or $v + 1 = u$).

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

theorem is_spanning_path_graph_pathGraph_three : is_spanning_path_graph (SimpleGraph.pathGraph 3) :=  ⟨1, fun a b => by simp [SimpleGraph.pathGraph_adj]⟩
See it in the graphDiscuss this resultChallenge it