AFTD Auto-Formalizing Theoretical Domains

is_oriented_star

def

A directed graph D is an oriented star with center c if it is loopless, asymmetric, every edge has c as an endpoint, and every other vertex is adjacent to c in one direction.

Statement

def is_oriented_star {V : Type*} (D : Digraph V) (c : V) : Prop
Defined in
arXiv:2611.15027, Section 6.1
Verified
15 Nov 2026
Axioms
none listed
Used by 1

Read back from the Lean

For a directed graph D on vertex type V and a vertex c : V, is_oriented_star D c asserts that D is an oriented star graph with center c. Specifically, it is the conjunction of four conditions: 1. D has no self-loops: for all v : V, ¬ D.Adj v v. 2. Every directed edge has c as its source or target: for all u, v : V, if D.Adj u v, then u = c or v = c. 3. D has no 2-cycles (is asymmetric): for all u, v : V, if D.Adj u v, then ¬ D.Adj v u. 4. Every vertex other than c is connected to c in at least one direction: for all u : V, if u ≠ c, then D.Adj c u or D.Adj u c.

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

/-- A digraph D is an oriented star with center c if every edge is incident to c, there are no loops or antiparallel edges, and every other vertex is adjacent to c. -/
def is_oriented_star {V : Type*} (D : Digraph V) (c : V) : Prop := (∀ v, ¬ D.Adj v v) ∧ (∀ u v, D.Adj u v → u = c ∨ v = c) ∧ (∀ u v, D.Adj u v → ¬ D.Adj v u) ∧ (∀ u, u ≠ c → (D.Adj c u ∨ D.Adj u c))
See it in the graphDiscuss this resultChallenge it