is_spanning_path_graph_pathGraph_three
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.
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.
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
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.
theorem is_spanning_path_graph_pathGraph_three : is_spanning_path_graph (SimpleGraph.pathGraph 3) := ⟨1, fun a b => by simp [SimpleGraph.pathGraph_adj]⟩