AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it