join_complete_turan
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
- join_complete_turan_fractional_cover_and_total_weightLet n, r, a be integers with r ≥ 3 and a ≤ n. The edge weighting w_a is a fractional K_r-cover of G_a = K_a ∨ T_{r-1}(n-a), and the total…
- join_complete_turan_decidableRelAdjacency in the join graph G_a = K_a ∨ T_{r-1}(n-a) on vertex set Fin a ⊕ Fin (n - a) is decidable.
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⟩ }