digraph_is_oriented
def
A digraph G : Digraph V on vertex type V is oriented (digraph_is_oriented G) if for all vertices u v : V, G.Adj u v implies ¬ G.Adj v u.
Statement
def digraph_is_oriented {V : Type*} (G : Digraph V) : Prop
- Defined in
- arXiv:2610.18600 Section 1
- Verified
- 23 Oct 2026
- Axioms
- none listed
- Used by 5
- digraph_is_oriented_botThe empty digraph (⊥ : Digraph V) on any vertex type V is oriented, satisfying digraph_is_oriented (⊥ : Digraph V).
- digraph_has_isolated_edge_card_ge_twoIf a finite oriented digraph G : Digraph V satisfies digraph_has_isolated_edge G and digraph_is_oriented G, then Fintype.card V ≥ 2.
- digraph_semisaturation_isolated_edge_boundIf G : Digraph V is a finite oriented digraph with DecidableEq V and DecidableRel G.Adj satisfying digraph_is_oriented G and…
- digraph_semisaturation_bounded_of_isolated_edgeLet G : Digraph V be a finite oriented digraph on vertex type V with DecidableEq V and DecidableRel G.Adj such that digraph_is_oriented G…
- digraph_is_semisaturatingA host digraph H : Digraph W on vertex type W semisaturates a digraph G : Digraph V on vertex type V (digraph_is_semisaturating H G) if…
Read back from the Lean
For a type V and a directed graph G : Digraph V, digraph_is_oriented G asserts that for all vertices u, v : V, if there is an edge from u to v (G.Adj u v), then there is no edge from v to u (¬ G.Adj v u) (i.e., the adjacency relation is asymmetric, which also precludes self-loops).
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 G is oriented if it contains no directed 2-cycles and no loops. -/ def digraph_is_oriented {V : Type*} (G : Digraph V) : Prop := ∀ u v, G.Adj u v → ¬ G.Adj v u