cycle_graph_six_book_ramsey_witness
In the 6-cycle graph on Fin 6, every pair of adjacent vertices has at most 0 common neighbors, and every pair of distinct non-adjacent vertices has at most 1 common neighbor in the complement graph.
Statement
theorem cycle_graph_six_book_ramsey_witness :
(∀ u v : Fin 6, (SimpleGraph.cycleGraph 6).Adj u v → Fintype.card ((SimpleGraph.cycleGraph 6).commonNeighbors u v) ≤ 0) ∧
(∀ u v : Fin 6, u ≠ v → ¬ (SimpleGraph.cycleGraph 6).Adj u v → Fintype.card ((SimpleGraph.cycleGraph 6)ᶜ.commonNeighbors u v) ≤ 1)- Formalizes
- arXiv:2610.36522 Appendix A -- Constructions for Nearly Diagonal Book Ramsey Numbers
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- book_ramsey_b1_b2_graph_existsThere exists a simple graph G on 6 vertices with decidable adjacency such that every pair of adjacent vertices has at most 0 common…
Read back from the Lean
A conjunction of two assertions about the cycle graph on 6 vertices (with vertex type Fin 6):
1. For all vertices $u, v : \text{Fin } 6$, if $u$ and $v$ are adjacent in SimpleGraph.cycleGraph 6, then the number of common neighbors of $u$ and $v$ in SimpleGraph.cycleGraph 6 (measured by Fintype.card) is at most 0 (i.e., equal to 0).
2. For all vertices $u, v : \text{Fin } 6$, if $u \ne v$ and $u$ and $v$ are not adjacent in SimpleGraph.cycleGraph 6, then the number of common neighbors of $u$ and $v$ in the complement graph (SimpleGraph.cycleGraph 6)ᶜ is at most 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
The theorem establishes that the 6-cycle graph $C_6$ witnesses the book Ramsey conditions for $n=2$ on 6 vertices: adjacent vertices share no common neighbors (reflecting that $C_6$ is triangle-free), and distinct non-adjacent vertices share at most one common neighbor in the complement graph. Because the vertex set $\mathrm{Fin}\ 6$ is finite and all graph-theoretic conditions are decidable, the entire theorem is proven by exhaustive finite computation.
Both conditions hold: adjacent vertices in $C_6$ have 0 common neighbors, and distinct non-adjacent vertices have at most 1 common neighbor in the complement $\overline{C_6}$. automation
Because the vertex set $\mathrm{Fin}\ 6$ is finite (having size 6), both conjuncts consist of bounded universal quantifiers over finite types. Graph adjacency, complementation, common neighbor sets, and cardinality comparisons are all decidable, so the `decide` tactic checks every pair $(u, v) \in \mathrm{Fin}\ 6 \times \mathrm{Fin}\ 6$ by finite computation and closes the goal.
decide
- The proof is carried out entirely by Lean's computational kernel via decision procedure: it exhaustively checks all pairs of vertices in Fin 6 rather than appealing to structural lemmas about cycle graphs.
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.
/-- The 6-cycle C_6 satisfies the book Ramsey conditions for n=2 on 6 vertices: every adjacent pair has at most 0 common neighbors, and every distinct non-adjacent pair has at most 1 common neighbor in the complement. -/theorem cycle_graph_six_book_ramsey_witness : (∀ u v : Fin 6, (SimpleGraph.cycleGraph 6).Adj u v → Fintype.card ((SimpleGraph.cycleGraph 6).commonNeighbors u v) ≤ 0) ∧ (∀ u v : Fin 6, u ≠ v → ¬ (SimpleGraph.cycleGraph 6).Adj u v → Fintype.card ((SimpleGraph.cycleGraph 6)ᶜ.commonNeighbors u v) ≤ 1) := by decide