# Question 834: An Explicit Directed Cycle Refutes Every Topological Order

[Return to catalogue page 5](https://ocme.evemisslab.com/en/questions/page/5/)

[← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261015-advance-20261116-r06-topological-ordering-dag-foundations/#q-20261015-advance-20261116-r06-topological-ordering-dag-0084)

This teaching derivation has second-context AI mathematical and bilingual semantic review, limited to the model and assumptions stated in this question. It has no human review or new Lean proof and does not promote the original question or MKO to Canonical truth.

P1000-0834 · q-20261015-advance-20261116-r06-topological-ordering-dag-0084



## Original question and givens

Use unique vertices=[v0, v1, v2, v3, v4, v5] and loop-free duplicate-free directed edges=[[v0, v1], [v1, v2], [v2, v0], [v0, v2], [v0, v5]]. Every edge u→v needs position(u)<position(v) in a complete vertex permutation; labels use source lexical order. Give (source_removal_trace, remaining_vertices, directed_cycle, cycle_detected, no_order_certificate, uniqueness_or_extra_claim, boundary).


- G001 — Use unique vertices=[v0, v1, v2, v3, v4, v5] and loop-free duplicate-free directed edges=[[v0, v1], [v1, v2], [v2, v0], [v0, v2], [v0, v5]]. Every edge u→v needs position(u)<position(v) in a complete vertex permutation; labels use source lexical order. Give (source_removal_trace, remaining_vertices, directed_cycle, cycle_detected, no_order_certificate, uniqueness_or_extra_claim, boundary).





## Definition and scope

When Kahn stops, give an edge-checked directed cycle; strict position inequalities around it make a topological order impossible.


- [mko-topological-ordering-dag](https://ocme.evemisslab.com/en/mko/mko-topological-ordering-dag/)





## Step-by-step derivation

S001 · impliesBefore

V=[v0, v1, v2, v3, v4, v5]

After

all directed edges=[[v0, v1], [v0, v2], [v0, v5], [v1, v2], [v2, v0]]

Conditions: none

This is a fully specified finite digraph, not necessarily a complete digraph.

Step identifiers and dependenciesRule: full_directed_graph · Uses: G001





S002 · impliesBefore

remaining=[v0, v1, v2, v3, v4, v5]; active edges=[[v0, v1], [v0, v2], [v0, v5], [v1, v2], [v2, v0]]

After

indegrees=[[v0, 1], [v1, 1], [v2, 2], [v3, 0], [v4, 0], [v5, 1]]; sources=[v3, v4]

Conditions: none

Recompute indegrees from remaining edges at every stage, rather than reusing original indegrees.

Step identifiers and dependenciesRule: remaining_indegree · Uses: G001, S001





S003 · impliesBefore

zero-indegree choices=[v3, v4]

After

choose=v3; new prefix=[v3]

Conditions: none

Choose the lexicographically first source and remove its outgoing edges.

Step identifiers and dependenciesRule: lexicographic_kahn_choice · Uses: G001, S002





S004 · impliesBefore

remaining=[v0, v1, v2, v4, v5]; active edges=[[v0, v1], [v0, v2], [v0, v5], [v1, v2], [v2, v0]]

After

indegrees=[[v0, 1], [v1, 1], [v2, 2], [v4, 0], [v5, 1]]; sources=[v4]

Conditions: none

Recompute indegrees from remaining edges at every stage, rather than reusing original indegrees.

Step identifiers and dependenciesRule: remaining_indegree · Uses: G001, S003





S005 · impliesBefore

zero-indegree choices=[v4]

After

choose=v4; new prefix=[v3, v4]

Conditions: none

Choose the lexicographically first source and remove its outgoing edges.

Step identifiers and dependenciesRule: lexicographic_kahn_choice · Uses: G001, S004





S006 · impliesBefore

remaining=[v0, v1, v2, v5]; active edges=[[v0, v1], [v0, v2], [v0, v5], [v1, v2], [v2, v0]]

After

indegrees=[[v0, 1], [v1, 1], [v2, 2], [v5, 1]]; sources=[]

Conditions: none

Recompute indegrees from remaining edges at every stage, rather than reusing original indegrees.

Step identifiers and dependenciesRule: remaining_indegree · Uses: G001, S005





S007 · impliesBefore

cycle candidate edge v0→v2

After

edge present: Yes

Conditions: none

Check every edge of the directed closed path returning to its start, not merely an impression that Kahn became stuck.

Step identifiers and dependenciesRule: cycle_edge_witness · Uses: G001, S006





S008 · impliesBefore

cycle candidate edge v2→v0

After

edge present: Yes

Conditions: none

Check every edge of the directed closed path returning to its start, not merely an impression that Kahn became stuck.

Step identifiers and dependenciesRule: cycle_edge_witness · Uses: G001, S007





S009 · impliesBefore

[v0, v2, v0]

After

pos(v0) < pos(v2) < pos(v0) is impossible

Conditions: none

A topological order would give a chain of strict position inequalities around the complete directed cycle, forcing the start before itself, a contradiction.

Step identifiers and dependenciesRule: strict_order_cycle_contradiction · Uses: G001, S008









## Reverse checks


- S009 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
- S008 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
- S007 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
- S006 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
- S005 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
- S004 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
- S003 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
- S002 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
- S001 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.





## Result

([[[v0, v1, v2, v3, v4, v5], [v3, v4], v3], [[v0, v1, v2, v4, v5], [v4], v4]], [v0, v1, v2, v5], [v0, v2, v0], Yes, Yes, No, directed_cycle_blocks_every_topological_order_while_multiple_orders_and_empty_edges_are_allowed)

The full substitutions and premise audits recover the original answer, retaining its field order and verdict meanings.





## This question review and source binding

Review date: 2026-10-26

Original questions, answers, step expressions, numeric ASTs and historical records are retained. Source candidate labels remain historical and are not overwritten as formal proof.

Source hashes and review receipts
- input commit: 0f7be61e2c22317a4075561dc822c87d881a50db
- original question SHA-256: 5e773ae3ae0055d540efdfb751750462cce847d35b22e69c9794d910e185ae1e
- candidate record SHA-256: f47842e9357b8fcd44cdca54b4345f440ff3b377ca9e66b0226173a62c72df3b
- semantic review receipt SHA-256: 6c2c6d46aded7582a11ac41a8c0b3bdde2669a53bdb6e796eea2039994a02772
- question-first witness SHA-256: 77e43898df9efdbf8094ad81fe4ab91cf4b4bd82f481eb9b4699b73cb4da612b
- Lean: NOT_RUN · human review: NOT_PERFORMED

[Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261015-advance-20261116-r06-topological-ordering-dag-0084.json)