AFTD Auto-Formalizing Theoretical Domains

SimpleGraphOrientation

structure

An orientation of a finite simple graph G assigns to each edge an ordered pair of its endpoints.

Statement

structure SimpleGraphOrientation {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj]
Defined in
Diestel, Graph Theory (5th ed. 2017), Section 1.5
Verified
11 Nov 2026
Axioms
none listed
Used by 5
  • cubic_stationary_entropy_infFor 0 < J < n, S_G(J) is the infimum of sum_e phi(j_e) among stationary currents j with |j_e| < 1 and sum_e |j_e| = J.
  • cubic_half_integral_saturated_edges_minFor a finite simple graph G with decidable equality and adjacency, and an orientation o of G, the invariant b(G) is the infimum in the…
  • op_1560_entropy_upper_bound_of_half_integralFor any finite simple graph G with orientation o and any half-integral stationary current j on G.edgeFinset with sum of |j(e)| equal to…
  • is_stationary_currentA current j on the edges of an oriented finite simple graph G is stationary if at every vertex, the sum of currents leaving the vertex…
  • is_stationary_current_zeroFor any finite simple graph G and any orientation o of G, the zero current assigning 0 to each edge is stationary.

Read back from the Lean

A structure SimpleGraphOrientation G parameterised by a finite type V with decidable equality, a simple graph G : SimpleGraph V, and decidable adjacency [DecidableRel G.Adj]. It consists of two fields: 1. dir: a function mapping each edge e : G.edgeFinset to an ordered pair of vertices (u, v) : V × V. 2. dir_fst_snd: the condition that for every edge e : G.edgeFinset, the unordered pair s((dir e).1, (dir e).2) in Sym2 V equals e.val (the edge e viewed as an unordered pair of vertices in G.edgeSet). In other words, it specifies an orientation of the simple graph G by choosing an ordered pair of endpoints for each undirected edge of G.

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

/-- An orientation of a simple graph assigns to each edge an ordered pair of its endpoints. -/
structure SimpleGraphOrientation {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] where
  dir : G.edgeFinset → V × V
  dir_fst_snd : ∀ e : G.edgeFinset, s((dir e).1, (dir e).2) = e.val
See it in the graphDiscuss this resultChallenge it