Topological ordering of a directed acyclic graph

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

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 — Use the directed graph model.
• Usual order on the real numbers — Specify ordering.
• Algorithm correctness — Retain the Kahn invariant.
• 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.