Question 848: An Explicit Directed Cycle Refutes Every Topological Order

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, v3], [v0, v4], [v1, v3]]. 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, v3], [v0, v4], [v1, v3]]. 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

Step-by-step derivation

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

all directed edges=[[v0, v1], [v0, v2], [v0, v3], [v0, v4], [v1, v2], [v1, v3], [v2, v0]]

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

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

zero-indegree choices=[v5]

choose=v5; new prefix=[v5]

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

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

cycle candidate edge v0→v2

edge present: Yes

cycle candidate edge v2→v0

edge present: Yes

[v0, v2, v0]

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

Reverse checks

• 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], [v5], v5]], [v0, v1, v2, v3, v4], [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.