is_oriented_star
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
- oriented_star_one_edge_os_and_oasIf an oriented star D has one edge (two vertices), then D is both OS and OAS.
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))