# Topological ordering of a directed acyclic graph

This English edition is an AI candidate and does not yet have an OCME Atlas (GPT-6) Twin closure receipt.

A finite directed graph has a topological ordering exactly when it has no directed cycle.

mko-topological-ordering-dag · theorem · v0.10.0



## Mathematical statement

A candidate ordering must be a permutation of all vertices and must place u before v for every edge u→v. For a small graph enumerate all valid orders. Kahn source removal chooses the lexically first zero-indegree vertex at each step and retains the trace. If no source exists while vertices remain, give an explicit directed cycle. Multiple orders and edgeless graphs are allowed; a zero-vertex graph has one empty order. One invalid candidate does not show the graph is cyclic. These graph orders are not topological-space notions.





## Representative formula (exact TeX)

O(G,p)=b





## Assumptions


- Vertices are finite and unique; directed edges are loop-free and duplicate-free.
- Complete permutation and cycle enumeration is restricted to bounded graphs.





## Symbol scope


- O — candidate topological order predicate
- G — finite directed graph
- p — vertex permutation
- b — candidate order validity boolean





## Intuition, definition, and misconceptions

Qualify the candidate permutation and audit every edge.

Cross-check complete enumeration with the Kahn trace.

An explicit cycle witness protects the reverse implication.

Notation candidate: b reports whether this specified permutation respects every directed edge of G,not acyclicity of G alone. Acyclicity is the separate existential statement that some topological order exists; an invalid candidate does not establish a cycle.

One invalid ordering does not make a graph cyclic, and a topological order need not be unique.





## Adopted derivation guide

[All permutations and a Kahn trace for a three-vertex DAG](https://ocme.evemisslab.com/en/derivations/derivation-mko-topological-ordering-dag-01/)The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.





## Prerequisites


- [Finite directed graph](https://ocme.evemisslab.com/en/mko/mko-finite-directed-graph/) — Use the directed graph model.
- [Usual order on the real numbers](https://ocme.evemisslab.com/en/mko/mko-order-relation/) — Specify ordering.
- [Algorithm correctness](https://ocme.evemisslab.com/en/mko/mko-algorithm-correctness/) — Retain the Kahn invariant.
- [Mathematical induction](https://ocme.evemisslab.com/en/mko/mko-mathematical-induction/) — Retain the general source-removal argument.





## Verification boundary

Finite enumeration certifies only the specified graph; the general equivalence still needs induction. The shared O(G,p)=b display assigns b an acyclic role, while candidate-order validity also depends on p: an invalid permutation order can occur in an acyclic graph. Preserve that unresolved role/scope alignment rather than treating a candidate-failure flag as graph cyclicity.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.





## Next obligation

Add linear extensions of partial orders.





## Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.

[Canonical MKO JSON](https://ocme.evemisslab.com/data/mko/source13-20261018-topological-ordering-dag.json) · [Plain Markdown](https://ocme.evemisslab.com/en/mko/mko-topological-ordering-dag/index.md)