AFTD Auto-Formalizing Theoretical Domains

join_complete_turan

def

The graph join G_a = K_a ∨ T_{r-1}(n-a) on vertex set Fin a ⊕ Fin (n - a), where vertices in Fin a form a clique, vertices in Fin (n - a) induce the Turán graph T_{r-1}(n-a), and all cross-edges between Fin a and Fin (n - a) are present.

Statement

def join_complete_turan (n r a : ℕ) : SimpleGraph (Fin a ⊕ Fin (n - a))
Defined in
arXiv:2610.41371, Section 3.1, eq. (3)
Verified
07 Nov 2026
Axioms
none listed
Used by 2

Read back from the Lean

Given natural numbers n, r, and a, join_complete_turan n r a is defined as the simple graph on the vertex type Fin a ⊕ Fin (n - a) with adjacency relation defined by: - Sum.inl u and Sum.inl v are adjacent if and only if u ≠ v (forming a complete graph on Fin a); - Sum.inr u and Sum.inr v are adjacent if and only if u and v are adjacent in SimpleGraph.turanGraph (n - a) (r - 1); - Sum.inl u and Sum.inr v are always adjacent; - Sum.inr u and Sum.inl v are always adjacent. That is, it is the graph join of the complete graph on a vertices and the Turán graph T(n - a, r - 1).

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 graph join of the complete graph K_a and the Turan graph T_{r-1}(n-a) on vertices Fin a ⊕ Fin (n - a). -/
def join_complete_turan (n r a : ℕ) : SimpleGraph (Fin a ⊕ Fin (n - a)) := {
  Adj
    | Sum.inl u, Sum.inl v => u ≠ v
    | Sum.inr u, Sum.inr v => (SimpleGraph.turanGraph (n - a) (r - 1)).Adj u v
    | Sum.inl _, Sum.inr _ => True
    | Sum.inr _, Sum.inl _ => True
  symm := ⟨by
    rintro (u | u) (v | v) h
    · exact h.symm
    · trivial
    · trivial
    · exact (SimpleGraph.turanGraph (n - a) (r - 1)).adj_symm h⟩
  loopless := ⟨by
    rintro (u | u) h
    · exact h rfl
    · exact (SimpleGraph.turanGraph (n - a) (r - 1)).loopless.irrefl u h⟩
}
See it in the graphDiscuss this resultChallenge it