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

[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-0068)

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-0818 · q-20261015-advance-20261116-r06-topological-ordering-dag-0068



## Original question and givens

Use unique vertices=[v0, v1, v2, v3, v4, v5] and loop-free duplicate-free directed edges=[[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, 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, 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, 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](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, v2], [v0, v5]]

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, v2], [v0, v5]]

After

indegrees=[[v0, 0], [v1, 0], [v2, 1], [v3, 0], [v4, 0], [v5, 1]]; sources=[v0, v1, 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=[v0, v1, v3, v4]

After

choose=v0; new prefix=[v0]

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=[v1, v2, v3, v4, v5]; active edges=[]

After

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

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

After

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

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=[v2, v3, v4, v5]; active edges=[]

After

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

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

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

After

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

Conditions: none

Choose the lexicographically first source and remove its outgoing edges.

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





S008 · impliesBefore

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

After

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

Conditions: none

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

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





S009 · impliesBefore

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

After

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

Conditions: none

Choose the lexicographically first source and remove its outgoing edges.

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





S010 · impliesBefore

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

After

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

Conditions: none

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

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





S011 · impliesBefore

zero-indegree choices=[v4, v5]

After

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

Conditions: none

Choose the lexicographically first source and remove its outgoing edges.

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





S012 · impliesBefore

remaining=[v5]; active edges=[]

After

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

Conditions: none

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

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





S013 · impliesBefore

zero-indegree choices=[v5]

After

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

Conditions: none

Choose the lexicographically first source and remove its outgoing edges.

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





S014 · impliesBefore

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

After

blocked=No; complete valid order=Yes

Conditions: none

Audit the final permutation edge by edge, retaining separate blocked and success flags.

Step identifiers and dependenciesRule: kahn_final_audit · Uses: G001, S013









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

Source hashes and review receipts
- input commit: 0f7be61e2c22317a4075561dc822c87d881a50db
- original question SHA-256: f32c65bccebfdd75e491e3b889c2b213bd74fe8e422c2b5b63a35cfa768c3a7a
- candidate record SHA-256: cfccc2886200a33954db864c583274592f8c08070ab578dc6cc9df8768efb7a7
- 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-0068.json)