alternating_path_two_adj_zero_one
In the alternating path AP_2 on Fin 2, vertices 0 and 1 are adjacent.
Statement
theorem alternating_path_two_adj_zero_one : (alternating_path 2).Adj ⟨0, by decide⟩ ⟨1, by decide⟩
- Source
- arXiv:2611.08375 "New results on cyclic and ordered Ramsey numbers", Section 1
- Verified
- 07 Nov 2026
- Axioms
Quot.soundpropext- Built on 2
- alternating_pathThe alternating path AP_n is the ordered simple graph on Fin n whose edges connect consecutive vertices in the alternating sequence 0,…
- alternating_path_vertexThe m-th vertex in the alternating path AP_n is m/2 if m is even, and n - 1 - m/2 if m is odd.
Read back from the Lean
In the graph alternating_path 2 (a SimpleGraph (Fin 2)), the vertex ⟨0, _⟩ and the vertex ⟨1, _⟩ are adjacent.
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
To show that vertices 0 and 1 are adjacent in the alternating path graph on two vertices, we unfold the graph's definition as a relation graph and rewrite the adjacency condition into distinctness and relation in at least one direction. The vertices are distinct, and setting the step index to $m = 0$ satisfies the edge relation because $0 + 1 < 2$ and the alternating path vertices at indices 0 and 1 evaluate definitionally to 0 and 1.
The values $0$ and $1$ are valid vertices in $\mathrm{Fin}\,2$.
The indices $0$ and $1$ require proofs that $0 < 2$ and $1 < 2$ to form terms of type $\mathrm{Fin}\,2$; both inequalities are checked by direct computation (`decide`).
(alternating_path 2).Adj ⟨0, by decide⟩ ⟨1, by decide⟩ := by
Adjacency in $\mathrm{alternating\_path}\,2$ reduces to showing that $0 \neq 1$ and that the pair satisfies the path relation in at least one direction.
Unfolding the definition of `alternating_path` expresses the graph as `SimpleGraph.fromRel` for the relation connecting consecutive vertices along the alternating path. Rewriting with `SimpleGraph.fromRel_adj` unfolds the definition of adjacency in such a graph into distinctness of the vertices and the relation holding in either direction.
uses
SimpleGraph.fromRel_adjunfold alternating_path rw [SimpleGraph.fromRel_adj]
Vertices $0$ and $1$ are adjacent in $\mathrm{alternating\_path}\,2$.
We satisfy the two conjuncts: first, $0 \neq 1$ in $\mathrm{Fin}\,2$ is verified by `decide`. Second, we prove the disjunction using `Or.inl` by providing $m = 0$ as the witness for the forward relation: the bound $0 + 1 < 2$ is checked by `decide`, and the equalities $\mathrm{val}(0) = \mathrm{alternating\_path\_vertex}\,2\,0$ and $\mathrm{val}(1) = \mathrm{alternating\_path\_vertex}\,2\,1$ hold by definition, discharged by reflexivity (`rfl`).
uses
Or.inlrefine ⟨by decide, Or.inl ⟨0, by decide, rfl, rfl⟩⟩
SimpleGraph.fromRel_adj- In a graph constructed from a binary relation $r$, vertices $v$ and $w$ are adjacent if and only if $v \neq w$ and either $r(v, w)$ or $r(w, v)$ holds.
Or.inl- From a proof of $a$, infer the disjunction $a \lor b$.
- Vertices in $\mathrm{Fin}\,2$ carry proofs that their underlying index is strictly less than $2$, discharged automatically by `decide`.
- The function `alternating_path_vertex` evaluates definitionally on small integers, so the vertex equality conditions hold by reflexivity (`rfl`).
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.
/-- In the alternating path AP_2, vertex 0 and vertex 1 are adjacent. -/theorem alternating_path_two_adj_zero_one : (alternating_path 2).Adj ⟨0, by decide⟩ ⟨1, by decide⟩ := by unfold alternating_path rw [SimpleGraph.fromRel_adj] refine ⟨by decide, Or.inl ⟨0, by decide, rfl, rfl⟩⟩