AFTD Auto-Formalizing Theoretical Domains

book_ramsey_b1_b2_graph_exists

theoremverifiedformalization

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

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

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

    line 6

    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.

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