monotone_cycle_three_adj_zero_one
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.
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.
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).
- The proof in Lean was generated by an automated search script that tries a sequence of candidate tactics (`first | ...`). This script happens to supply the unrelated lemma `digraph_safe17_four_triangles` to `simpa`. In reality, once `monotone_cycle` is unfolded, the simplifier reduces the goal to true purely through basic arithmetic ($0 + 1 = 1$ and $0 \neq 1$), without using `digraph_safe17_four_triangles` at all.
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 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)