Question 811: Remove the Lexically First Zero-Indegree Source at Each Kahn Step

Original question and givens

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

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

Definition and scope

Each round recomputes indegrees from the remaining edges and removes the lexicographically first zero-indegree vertex.

• mko-topological-ordering-dag

Step-by-step derivation

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

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

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

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

zero-indegree choices=[v0, v3, v5]

choose=v0; new prefix=[v0]

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

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

zero-indegree choices=[v1, v2, v3, v4, v5]

choose=v1; new prefix=[v0, v1]

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

indegrees=[[v2, 0], [v3, 0], [v4, 0], [v5, 0]]; sources=[v2, v3, v4, v5]

zero-indegree choices=[v2, v3, v4, v5]

choose=v2; new prefix=[v0, v1, v2]

remaining=[v3, v4, v5]; active edges=[]

indegrees=[[v3, 0], [v4, 0], [v5, 0]]; sources=[v3, v4, v5]

zero-indegree choices=[v3, v4, v5]

choose=v3; new prefix=[v0, v1, v2, v3]

remaining=[v4, v5]; active edges=[]

indegrees=[[v4, 0], [v5, 0]]; sources=[v4, v5]

zero-indegree choices=[v4, v5]

choose=v4; new prefix=[v0, v1, v2, v3, v4]

remaining=[v5]; active edges=[]

indegrees=[[v5, 0]]; sources=[v5]

zero-indegree choices=[v5]

choose=v5; new prefix=[v0, v1, v2, v3, v4, v5]

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

blocked=No; complete valid order=Yes

Reverse checks

• S014 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
• S013 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
• S012 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
• S011 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
• S010 · premise_and_result_audit — Audit all vertices and edges; one failed order is not a cycle proof, and no legal branch may be omitted.
• 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], [v0, v3, v5], v0], [[v1, v2, v3, v4, v5], [v1, v2, v3, v4, v5], v1], [[v2, v3, v4, v5], [v2, v3, v4, v5], v2], [[v3, v4, v5], [v3, v4, v5], v3], [[v4, v5], [v4, v5], v4], [[v5], [v5], v5]], [v0, v1, v2, v3, v4, v5], No, Yes, each_step_removes_lexicographically_first_zero_indegree_source)

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.