AFTD Auto-Formalizing Theoretical Domains

petersen_ramsey_red_graph

def

The red graph G_R on 20 vertices, defined as the disjoint union of two complete graphs of order 9 and one complete graph of order 2.

Statement

def petersen_ramsey_red_graph : SimpleGraph (Fin 20)
Defined in
arXiv:2611.09347 Section 3
Verified
09 Nov 2026
Axioms
none listed
Used by 1
  • petersen_ramsey_blue_graphThe blue graph G_B on 20 vertices, defined as the graph complement of the red graph G_R, isomorphic to the join graph K_{9,9} ∨ K_2ᶜ.

Read back from the Lean

Definition of petersen_ramsey_red_graph as the SimpleGraph on vertex type Fin 20 where two vertices u and v are adjacent if and only if u ≠ v and at least one of the following holds: 1. u.val < 9 and v.val < 9, 2. 9 ≤ u.val < 18 and 9 ≤ v.val < 18, or 3. 18 ≤ u.val and 18 ≤ v.val. (Equivalently, the disjoint union of complete graphs $K_9$, $K_9$, and $K_2$ on $\{0, \dots, 8\}$, $\{9, \dots, 17\}$, and $\{18, 19\}$.)

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- The red graph on 20 vertices for the Petersen Ramsey lower bound, formed by the disjoint union of two copies of K_9 and one copy of K_2. -/
def petersen_ramsey_red_graph : SimpleGraph (Fin 20) := {
  Adj := fun u v => u ≠ v ∧ ((u.val < 9 ∧ v.val < 9) ∨ (9 ≤ u.val ∧ u.val < 18 ∧ 9 ≤ v.val ∧ v.val < 18) ∨ (18 ≤ u.val ∧ 18 ≤ v.val))
  symm := ⟨fun u v h => by
    rcases h with ⟨hne, h | h | h⟩
    · exact ⟨hne.symm, Or.inl ⟨h.2, h.1⟩⟩
    · exact ⟨hne.symm, Or.inr (Or.inl ⟨h.2.2.1, h.2.2.2, h.1, h.2.1⟩)⟩
    · exact ⟨hne.symm, Or.inr (Or.inr ⟨h.2, h.1⟩)⟩⟩
  loopless := ⟨fun u h => h.1 rfl⟩
}
See it in the graphDiscuss this resultChallenge it