AFTD Auto-Formalizing Theoretical Domains

monotone_cycle_three_adj_zero_one

theoremverified

In the monotone cycle MC_3 on Fin 3, vertices 0 and 1 are adjacent.

Statement

theorem monotone_cycle_three_adj_zero_one :
    (monotone_cycle 3).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
  • monotone_cycleThe monotone cycle MC_k is the ordered simple graph on Fin k with edges {i, i+1} for 0 ≤ i < k-1 and the edge {0, k-1}.
  • digraph_safe17_four_trianglesThe displayed graph contains the four explicit directed triangles on vertices 0,1,4; 2,3,6; 5,7,9; and 8,10,12.

Read back from the Lean

In the simple graph monotone_cycle 3 on vertices Fin 3, the vertex ⟨0, _⟩ is adjacent to the vertex ⟨1, _⟩.

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 monotone cycle $MC_3$, we unfold the definition of `monotone_cycle`. Adjacency holds if $a + 1 = b$ or $(a = 0 \land b + 1 = 3)$ (or vice versa) with $a \neq b$. For $a = 0$ and $b = 1$, the first disjunct $0 + 1 = 1$ holds, so the relation is satisfied and Lean's simplifier closes the goal.

  1. Vertices 0 and 1 are adjacent in the monotone cycle on 3 vertices, `monotone_cycle 3`. automation

    The definition of `monotone_cycle 3` is unfolded: for $k = 3$, an edge exists between distinct vertices $a, b \in \mathrm{Fin}\,3$ if $a + 1 = b$ or ($a = 0$ and $b + 1 = 3$), or the symmetric relation. For $a = 0$ and $b = 1$, the condition $0 + 1 = 1$ holds and $0 \neq 1$. The automated simplifier discharges this arithmetic verification and closes the goal.

    line 3

    uses digraph_safe17_four_triangles

        (monotone_cycle 3).Adj ⟨0, by decide⟩ ⟨1, by decide⟩ := by first | exact digraph_safe17_four_triangles | (apply digraph_safe17_four_triangles <;> assumption) | (apply digraph_safe17_four_triangles <;> simp_all) | simpa using digraph_safe17_four_triangles | (simp only [monotone_cycle] at *; first | exact digraph_safe17_four_triangles | (apply digraph_safe17_four_triangles <;> assumption) | (apply digraph_safe17_four_triangles <;> simp_all) | simpa using digraph_safe17_four_triangles)
digraph_safe17_four_triangles
In the graph `digraph_safe17_graph`, there exist four disjoint triangles on specific vertex triples (0-1-4, 2-3-6, 5-7-9, and 8-10-12).

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 monotone cycle MC_3, vertex 0 and vertex 1 are adjacent. -/theorem monotone_cycle_three_adj_zero_one :    (monotone_cycle 3).Adj ⟨0, by decide⟩ ⟨1, by decide⟩ := by first | exact digraph_safe17_four_triangles | (apply digraph_safe17_four_triangles <;> assumption) | (apply digraph_safe17_four_triangles <;> simp_all) | simpa using digraph_safe17_four_triangles | (simp only [monotone_cycle] at *; first | exact digraph_safe17_four_triangles | (apply digraph_safe17_four_triangles <;> assumption) | (apply digraph_safe17_four_triangles <;> simp_all) | simpa using digraph_safe17_four_triangles)
See it in the graphDiscuss this resultChallenge it