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

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

Step-by-step derivation

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

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

count v0 in candidate

count(v0)=1

count v1 in candidate

count(v1)=1

count v2 in candidate

count(v2)=1

count v3 in candidate

count(v3)=1

count v4 in candidate

count(v4)=1

count v5 in candidate

count(v5)=1

edge v0→v1

pos(v0)=0; pos(v1)=1; 0<1: Yes

edge v0→v2

pos(v0)=0; pos(v2)=2; 0<2: Yes

edge v0→v3

pos(v0)=0; pos(v3)=3; 0<3: Yes

edge v0→v5

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

permutation=Yes; every edge passes=Yes

valid topological order=Yes

Reverse checks

• S012 · premise_and_result_audit — A failed candidate does not prove a cycle; the proposed permutation may simply be wrong.
• S011 · premise_and_result_audit — One passing edge cannot stand in for all edges.
• S010 · premise_and_result_audit — One passing edge cannot stand in for all edges.
• S009 · premise_and_result_audit — One passing edge cannot stand in for all edges.
• 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, v1], 0, 1, Yes], [[v0, v2], 0, 2, Yes], [[v0, v3], 0, 3, 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.