is_graph_orientation
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
- orientation_out_degree_le_degreeIn any orientation D of a finite simple graph G, the out-degree of any vertex v in D is at most the degree of v in G.
- orientation_perfect_matching_sign_eq_one_or_neg_oneIf D is an orientation of a simple graph G on Fin n (is_graph_orientation G D) and M is a perfect matching of G, then…
- digraph_eulerian_orientation_arborescence_count_posAn Eulerian orientation D of a finite connected simple graph is strongly connected, so for every root r it has at least one spanning…
- cycle_graph_eight_strong_orientation_diameter_le_sevenSanity (non-vacuity): the 8-cycle, a bridgeless graph of diameter 4, has a strong orientation of directed diameter at most 7, namely the…
- oriented_diameter_bound_holds_monoIf every connected bridgeless graph of diameter d has a strong orientation of diameter at most k, the same holds for every k' >= k (f(d)…
- digraph_is_alternating_orientationFor a simple graph G, a permutation σ : Equiv.Perm G.Dart of the darts of G (in use, a rotation system: the cyclic order of darts around…
- digraph_alternating_orientation_unique_up_to_reversalOn any connected graph with a rotation system σ, an alternating orientation is uniquely determined up to reversal: any two alternating…
- orientation_tuple_is_pfaffian_of_rows_differ_in_halfLet k ≥ 1, let G be a simple graph on Fin n and let D : Fin (2k) → Digraph (Fin n) be a 2k-tuple of orientations of G…
- digraph_is_eulerian_orientation_of_alternatingAn alternating orientation (for any rotation system) is Eulerian: around each vertex σ maps outgoing darts bijectively to incoming ones…
- oriented_diameter_four_lower_boundf(4) >= 12: there is a finite connected bridgeless simple graph of diameter 4 that has no strong orientation of directed diameter at most…
- digraph_is_eulerian_orientationFor a simple graph G and a digraph D on the vertex type Fin n (as for digraph_arborescence_count_at), D is an Eulerian orientation of G:…
- has_strong_orientation_of_diameter_leThe simple graph G has an orientation D (each edge of G gets exactly one direction, no other arcs) in which every ordered pair of vertices…
- digraph_eulerian_orientation_reversalThe reversal of an Eulerian orientation of a simple graph is also an Eulerian orientation.
- digraph_is_alternating_orientation_reversalThe reversal of an alternating orientation of a graph for a rotation system σ is also an alternating orientation for σ.
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)