AFTD Auto-Formalizing Theoretical Domains

is_graph_orientation

def

A digraph D is an orientation of a simple graph G if every edge of G is assigned exactly one direction in D, and non-adjacent pairs in G are not adjacent in D.

Statement

def is_graph_orientation {V : Type*} (G : SimpleGraph V) (D : Digraph V) : Prop
Defined in
arXiv:2610.09648 Section 1
Verified
19 Oct 2026
Axioms
none listed
Used by 14

Read back from the Lean

For a type V, a simple graph G with vertex type V, and a directed graph D with vertex type V, is_graph_orientation G D asserts that: 1. For all vertices u, v : V, there is a directed edge between u and v in D in at least one direction (D.Adj u v ∨ D.Adj v u) if and only if u and v are adjacent in G (G.Adj u v); and 2. For all vertices u, v : V, it is not the case that both D.Adj u v and D.Adj v u hold simultaneously. In other words, D is an orientation of G: every undirected edge in G is assigned exactly one direction in D, and D contains no self-loops or bidirected edges.

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 orientation of a simple graph G. -/
def is_graph_orientation {V : Type*} (G : SimpleGraph V) (D : Digraph V) : Prop := (∀ u v, D.Adj u v ∨ D.Adj v u ↔ G.Adj u v) ∧ ∀ u v, ¬(D.Adj u v ∧ D.Adj v u)
See it in the graphDiscuss this resultChallenge it