digraph_is_oriented_bot
The empty digraph (⊥ : Digraph V) on any vertex type V is oriented, satisfying digraph_is_oriented (⊥ : Digraph V).
Statement
theorem digraph_is_oriented_bot (V : Type*) : digraph_is_oriented (⊥ : Digraph V)
- Source
- folklore
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- digraph_is_orientedA digraph G : Digraph V on vertex type V is oriented (digraph_is_oriented G) if for all vertices u v : V, G.Adj u v implies ¬ G.Adj v u.
Read back from the Lean
For any type V, the bottom directed graph ⊥ : Digraph V satisfies digraph_is_oriented, meaning that for all vertices u, v : V, if u is adjacent to v in ⊥, then v is not adjacent to u in ⊥.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
A directed graph is oriented if no pair of vertices has edges in both directions. In the empty graph ⊥, there are no edges between any vertices, so the condition holds vacuously.
The empty digraph satisfies the orientedness condition vacuously. automation
Unfolding the definition of an oriented digraph (`digraph_is_oriented`), we must show that for any vertices $u$ and $v$, if there is a directed edge from $u$ to $v$ in the empty graph $\bot$, then there is no directed edge from $v$ to $u$. Since the empty graph has no edges, the antecedent is false, so the implication holds vacuously; the simplifier discharges this by replacing the empty adjacency with false and simplifying the implication.
uses
digraph_is_orientedsimp [digraph_is_oriented]
digraph_is_oriented- A directed graph is oriented if no pair of vertices has edges in both directions: for all vertices u and v, if there is an edge from u to v, then there is no edge from v to u.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The empty digraph is oriented. -/theorem digraph_is_oriented_bot (V : Type*) : digraph_is_oriented (⊥ : Digraph V) := by simp [digraph_is_oriented]