All permutations and a Kahn trace for a three-vertex DAG

Goal and scope

List every valid order and audit source-removal invariants.

Finite graph orders, not topological spaces.

Givens and symbols

• work

• G1 — V={0,1,2}, E={(0,2),(1,2)}; Kahn selects the least zero-indegree vertex at each step.

• V,E — complete vertex and edge sets
• pos — order position

Rules and sources

• mko_definition · cited — 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. · mko-topological-ordering-dag
• work · prerequisite — A topological order is a full vertex permutation with pos(u)<pos(v) for every edge u-to-v; Kahn removes a zero-indegree source and updates the residual graph. A DAG has no directed cycle; a topological order is a full vertex permutation placing each edge's source strictly before its target.

Main derivation

\text{all permutations of }V

012,021,102,120,201,210

012,102

\operatorname{pos}(0)<\operatorname{pos}(2),\quad\operatorname{pos}(1)<\operatorname{pos}(2)

021,120

021\text{ violates }1\to2;\quad120\text{ violates }0\to2

201,210

\text{both violate }0\to2\text{ since2 precedes0}

d^-(0,1,2)=(0,0,2)

\text{Kahn chooses }0;\quad\text{remaining indegrees }(1:0,2:1)

\text{remaining }\{1,2\},\quad d^-=(0,1)

\text{choose }1,\text{ then }2;\quad\text{output }012

H:\ E_H=\{(0,1),(1,2),(2,0)\}

d^-_H=(1,1,1),\quad0\to1\to2\to0\text{ is a cycle}

\operatorname{Orders}(G)=\{012,102\}

G\text{ is a DAG and Kahn returns }012

Substeps and lemmas

No substeps in this guide.

Reverse audits

• S08 · premise_audit · G1, S07, work — A zero-vertex graph has one empty order; a nonempty edgeless graph has every permutation.
• S07 · premise_audit · G1, S06, work — Do not leave the cycle certificate implicit in Kahn stopping.
• S06 · premise_audit · G1, S05, work — Each source deletion keeps the output prefix free of violated incoming edges.
• S05 · premise_audit · G1, S04, work — Track indegrees in the remaining graph, not initial values.
• S04 · premise_audit · G1, S03, work — The valid orders are exactly012 and 102, so they are not unique.
• S03 · premise_audit · G1, S02, work — Their failure does not make the original graph cyclic.
• S02 · premise_audit · G1, S01, work — Both edges, not only0-to2, must be checked.
• S01 · premise_audit · G1, work — Sequences with duplicates or omissions are excluded.

Error controls and negative controls

Six permutations

Each of the 3! candidates appears once, with edge evidence for its validity or failure.

Residual graph

Delete outgoing edges and update indegrees at every step.

• Invalid021 means the graph has a cycle. → reject — 012 is a complete valid order.
• This graph has a unique topological order. → reject — Both012 and 102 are valid.
• Removing0 immediately makes2 a source. → reject — The edge1-to2 remains, leaving indegree1.

Result and limitations

All valid orders are 012,102; lex-first Kahn outputs012 and the graph is a DAG.

Verification and source binding

2 declared checks for this guide; only the listed expressions are covered.

• source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
• adopted source SHA-256: 75e458baf0ea665f57f182f5f2532425a1c004b4b86bffc40d16191b5e5c83e3
• original source SHA-256: 28d6cd464a04e9680e5cb6230b6ecb75b0de6ea8867e0fa97d61121a6898906c
• Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW

Same-source full JSON (formulas, ASTs, controls and revision log)