book_ramsey_b1_b2_graph_exists
There exists a simple graph G on 6 vertices with decidable adjacency such that every pair of adjacent vertices has at most 0 common neighbors in G, and every pair of distinct non-adjacent vertices has at most 1 common neighbor in the complement graph Gᶜ.
Statement
theorem book_ramsey_b1_b2_graph_exists :
∃ (G : SimpleGraph (Fin 6)) (_ : DecidableRel G.Adj),
(∀ u v : Fin 6, G.Adj u v → Fintype.card (G.commonNeighbors u v) ≤ 0) ∧
(∀ u v : Fin 6, u ≠ v → ¬ G.Adj u v → Fintype.card (Gᶜ.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- Built on 1
- cycle_graph_six_book_ramsey_witnessIn 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…
Read back from the Lean
There exists a simple graph $G$ on the vertex type Fin 6 with a decidable adjacency relation such that both of the following hold:
1. For all vertices $u, v : \text{Fin } 6$, if $u$ and $v$ are adjacent in $G$, then the number of common neighbors of $u$ and $v$ in $G$ 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 $G$, then the number of common neighbors of $u$ and $v$ in the complement graph $G^c$ 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 existence theorem is proved constructively by exhibiting the 6-cycle graph $C_6$ as an explicit witness. An existential tuple is formed with $C_6$, its synthesized decidability instance, and the helper theorem `cycle_graph_six_book_ramsey_witness`, which establishes that $C_6$ is triangle-free and that no two non-adjacent vertices share more than one neighbor in the complement graph $C_6^c$.
The 6-cycle $C_6$ on 6 vertices satisfies the Ramsey $(B_1, B_2; 6)$ conditions.
The existential goal requires a graph $G$ on 6 vertices, a proof that adjacency in $G$ is decidable, and proofs of the two neighborhood conditions. The proof supplies an explicit witness tuple: the cycle graph on 6 vertices ($C_6$, written `SimpleGraph.cycleGraph 6`), the decidability instance inferred by typeclass resolution (`inferInstance`), and the lemma `cycle_graph_six_book_ramsey_witness`, which certifies that adjacent vertices share no common neighbors and distinct non-adjacent vertices share at most 1 common neighbor in the complement graph $C_6^c$.
uses
cycle_graph_six_book_ramsey_witness⟨SimpleGraph.cycleGraph 6, inferInstance, cycle_graph_six_book_ramsey_witness⟩
cycle_graph_six_book_ramsey_witness- In the 6-cycle graph on vertices {0, ..., 5}, any two adjacent vertices have at most 0 common neighbors, and any two distinct non-adjacent vertices have at most 1 common neighbor in the complement graph.
- The proof is given as a single term rather than a sequence of tactics.
- The decidability of adjacency (`inferInstance`) is a formal typeclass requirement enabling `Fintype.card` to count common neighbors; it has no mathematical counterpart on paper.
- The actual combinatorial verification that $C_6$ satisfies the neighborhood constraints is outsourced to `cycle_graph_six_book_ramsey_witness`.
Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
/-- Existence of a Ramsey (B_1, B_2; 6) graph on 6 vertices, establishing the base case n=2 of nearly diagonal book Ramsey lower bounds. -/theorem book_ramsey_b1_b2_graph_exists : ∃ (G : SimpleGraph (Fin 6)) (_ : DecidableRel G.Adj), (∀ u v : Fin 6, G.Adj u v → Fintype.card (G.commonNeighbors u v) ≤ 0) ∧ (∀ u v : Fin 6, u ≠ v → ¬ G.Adj u v → Fintype.card (Gᶜ.commonNeighbors u v) ≤ 1) := ⟨SimpleGraph.cycleGraph 6, inferInstance, cycle_graph_six_book_ramsey_witness⟩