AFTD Auto-Formalizing Theoretical Domains

alternating_path_two_adj_zero_one

theoremverified

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.

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

    line 3

        (alternating_path 2).Adj ⟨0, by decide⟩ ⟨1, by decide⟩ := by
  2. 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.

    lines 4–5

    uses SimpleGraph.fromRel_adj

      unfold alternating_path
      rw [SimpleGraph.fromRel_adj]
  3. 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`).

    line 6

    uses Or.inl

      refine ⟨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$.

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

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