AFTD Auto-Formalizing Theoretical Domains

simple_graph_is_orientation

def

A digraph D is an orientation of a simple graph G if every directed edge of D is an edge of G and for every edge of G exactly one of the two directed edges is present in D.

Statement

def simple_graph_is_orientation {V : Type*} (D : Digraph V) (G : SimpleGraph V) : Prop
Defined in
scout/2610-09648-an-asymptotically-tight-bound-on-oriented-diameter.md:101
Verified
24 Oct 2026
Axioms
none listed

Read back from the Lean

For a type V, a directed graph D on V, and a simple graph G on V, simple_graph_is_orientation D G is the proposition that: 1. For all vertices u, v : V, if there is a directed edge from u to v in D (D.Adj u v), then u and v are adjacent in G (G.Adj u v). 2. For all vertices u, v : V, if u and v are adjacent in G (G.Adj u v), then there is a directed edge from u to v in D if and only if there is no directed edge from v to u in D (D.Adj u v ↔ ¬ D.Adj v u).

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 an undirected simple graph G if its edges are directed edges of G with exactly one direction chosen for each undirected edge of G. -/
def simple_graph_is_orientation {V : Type*} (D : Digraph V) (G : SimpleGraph V) : Prop := (∀ u v, D.Adj u v → G.Adj u v) ∧ ∀ u v, G.Adj u v → (D.Adj u v ↔ ¬ D.Adj v u)
See it in the graphDiscuss this resultChallenge it