AFTD Auto-Formalizing Theoretical Domains

cycle_graph_six_book_ramsey_witness

theoremverifiedformalization

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.

  1. 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.

    line 5

      decide

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

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