# Question 216: Vertex-Set Equality Is Not Yet a Complete Valid Topological Permutation

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

[← 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-0016)

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.

P250-0216 · q-20261015-advance-20261116-r06-topological-ordering-dag-0016



## Original question and givens

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


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





## Definition and scope

For the finite digraph, require a complete vertex permutation and source-before-target order for every edge.


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

After

length(candidate)=6, |V|=6

Conditions: none

A topological order must list every vertex exactly once; first compare the lengths.

Step identifiers and dependenciesRule: permutation_domain · Uses: G001





S002 · impliesBefore

count v0 in candidate

After

count(v0)=1

Conditions: none

Check the multiplicity of each vertex to detect omissions and duplicates.

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





S003 · impliesBefore

count v1 in candidate

After

count(v1)=1

Conditions: none

Check the multiplicity of each vertex to detect omissions and duplicates.

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





S004 · impliesBefore

count v2 in candidate

After

count(v2)=1

Conditions: none

Check the multiplicity of each vertex to detect omissions and duplicates.

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





S005 · impliesBefore

count v3 in candidate

After

count(v3)=1

Conditions: none

Check the multiplicity of each vertex to detect omissions and duplicates.

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





S006 · impliesBefore

count v4 in candidate

After

count(v4)=1

Conditions: none

Check the multiplicity of each vertex to detect omissions and duplicates.

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





S007 · impliesBefore

count v5 in candidate

After

count(v5)=1

Conditions: none

Check the multiplicity of each vertex to detect omissions and duplicates.

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





S008 · impliesBefore

edge v0→v5

After

pos(v0)=0; pos(v5)=5; 0<5: Yes

Conditions: none

Every directed edge requires its source before its target; positions are zero-based.

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





S009 · impliesBefore

permutation=Yes; every edge passes=Yes

After

valid topological order=Yes

Conditions: none

The full permutation and every edge constraint must both hold; this is exactly the definition for this finite graph.

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









## Reverse checks


- S009 · premise_and_result_audit — A failed candidate does not prove a cycle; the proposed permutation may simply be wrong.
- S008 · premise_and_result_audit — One passing edge cannot stand in for all edges.
- S007 · premise_and_result_audit — A full permutation requires multiplicity 1 for every vertex and no outside label.
- S006 · premise_and_result_audit — A full permutation requires multiplicity 1 for every vertex and no outside label.
- S005 · premise_and_result_audit — A full permutation requires multiplicity 1 for every vertex and no outside label.
- S004 · premise_and_result_audit — A full permutation requires multiplicity 1 for every vertex and no outside label.
- S003 · premise_and_result_audit — A full permutation requires multiplicity 1 for every vertex and no outside label.
- S002 · premise_and_result_audit — A full permutation requires multiplicity 1 for every vertex and no outside label.
- S001 · premise_and_result_audit — Equal underlying sets are not enough: duplicate entries may still invalidate the candidate.





## Result

([v0, v1, v2, v3, v4, v5], [v0, v1, v2, v3, v4, v5], Yes, [[[v0, v5], 0, 5, Yes]], Yes, invalid_candidate_does_not_itself_prove_a_cycle)

Is this candidate a valid topological order? Yes.





## This question review and source binding

Review date: 2026-10-24

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: 747e308d3ccae6163aa0a920a9cdc09ff65d09b84770aa4ac0cfd10e9ecb852f
- candidate record SHA-256: a0341e2b8bf51f6ab4eb0ae382e7ea90cfa3c59c4cc0b7db3dfbac663c57c126
- semantic review receipt SHA-256: 4727d1bd957a9b7f6cadb7972ddb5ab80a31f5259dc5394c1dff2b71944ed36b
- question-first witness SHA-256: 51e18649133238ac992229f6e16542a5f3af53ca73b2262ab0524508ea937dee
- 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-0016.json)