double_star_graph
The double star graph S_{a,b} on vertex set Bool ⊕ Fin a ⊕ Fin b, with centers Sum.inl false and Sum.inl true joined by an edge, and with a leaves attached to Sum.inl false and b leaves attached to Sum.inl true.
Statement
def double_star_graph (a b : ℕ) : SimpleGraph (Bool ⊕ Fin a ⊕ Fin b)- Defined in
- arXiv:2611.15124 Section 2.2, Domination in token graphs of graphs with domination number two
- Verified
- 15 Nov 2026
- Axioms
- none listed
Read back from the Lean
Given natural numbers a and b, double_star_graph a b defines a simple graph on the vertex type Bool ⊕ Fin a ⊕ Fin b constructed via SimpleGraph.fromRel from the binary relation relating x to y if and only if:
1. x = Sum.inl false and y = Sum.inl true, or
2. there exists i : Fin a such that x = Sum.inl false and y = Sum.inr (Sum.inl i), or
3. there exists j : Fin b such that x = Sum.inl true and y = Sum.inr (Sum.inr j).
Because SimpleGraph.fromRel takes the symmetric and irreflexive closure, two vertices u and v are adjacent in this graph if and only if they are distinct and either relates to the other, giving an undirected edge between Sum.inl false and Sum.inl true, an edge between Sum.inl false and each Sum.inr (Sum.inl i) (for i : Fin a), and an edge between Sum.inl true and each Sum.inr (Sum.inr j) (for j : Fin b).
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 double star S_{a,b} on vertex type Bool ⊕ Fin a ⊕ Fin b. -/ def double_star_graph (a b : ℕ) : SimpleGraph (Bool ⊕ Fin a ⊕ Fin b) := SimpleGraph.fromRel fun x y => (x = Sum.inl false ∧ y = Sum.inl true) ∨ (∃ i : Fin a, x = Sum.inl false ∧ y = Sum.inr (Sum.inl i)) ∨ (∃ j : Fin b, x = Sum.inl true ∧ y = Sum.inr (Sum.inr j))