is_layered_dag
def
A digraph G is a layered DAG with layer function layer : V → ℕ if every directed edge connects a vertex in layer i to a vertex in layer i + 1.
Statement
def is_layered_dag {V : Type*} (G : Digraph V) (layer : V → ℕ) : Prop
- Defined in
- arXiv:2611.07043
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Used by 1
- layered_digraph_compatible_family_common_vertexLet G = (V, E) be a directed graph on a vertex type V, let L be a positive natural number (0 < L), and let layer : V → ℕ be a layer…
Read back from the Lean
Given a type V, a directed graph G : Digraph V, and a function layer : V → ℕ, is_layered_dag G layer asserts that for all vertices u, v : V, if u is adjacent to v in G (G.Adj u v), then the layer of v is one greater than the layer of u (layer v = layer u + 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
/-- A digraph is a layered DAG if vertices have layer indices and every directed edge goes from a layer to the next layer. -/ def is_layered_dag {V : Type*} (G : Digraph V) (layer : V → ℕ) : Prop := ∀ u v, G.Adj u v → layer v = layer u + 1