# Orientation, all degrees and a walk audit

[← Guide index](https://ocme.evemisslab.com/en/derivations/) · [Original MKO](https://ocme.evemisslab.com/en/mko/mko-finite-directed-graph/)

This is an owner-adopted natural-language teaching guide. Finite/arithmetic checks are not universal proofs; no Lean was run, and review scope is recorded per revision. Original source status labels are retained as historical data. Formulas retain exact TeX; no new semantic AST is invented.

derivation-mko-finite-directed-graph-01 · ocme-new142-reader-adoption-20261021



## Goal and scope

Audit a fully specified digraph under the declared loop-free simple convention.

n≥1; no undirected-degree or loop-model substitution.





## Givens and symbols


- work


- G1 — V={0,1,2}, directed E={(0,1),(1,0),(1,2)}, in lexicographic order; candidate walk W=(0,1,2).


- V,E — complete vertex and edge sets
- d+,d- — out- and in-degree





## Rules and sources


- mko_definition · cited — Each edge is (u,v) with u≠v; (u,v) and (v,u) are different edges. Edges form a set, so same-direction parallel duplicates are forbidden. In-degrees and out-degrees are separate, each summing over the whole graph to |E|. Successive walk steps must follow orientation. Explicit loop boundaries fail this declared model, not every possible digraph convention. · mko-finite-directed-graph
- work · prerequisite — Directed edges are ordered pairs; out-degree counts first coordinates and in-degree second coordinates; walks respect each orientation. Edges of a simple loop-free digraph are unique ordered pairs with distinct endpoints; a reverse pair is a distinct edge; every directed-walk step must belong to E in that orientation.





## Main derivation

S01 · impliesBefore

E=((0,1),(1,0),(1,2))

After

\text{unique ordered pairs, all endpoints in }V,\quad u\ne v

Conditions: none

Rule: work · Uses: G1, work

Leaf basis: work

All three ordered pairs are legal, unique and loop-free.



S02 · impliesBefore

v=0

After

d^+(0)=1,\quad d^-(0)=1

Conditions: none

Rule: work · Uses: G1, S01, work

Leaf basis: work

Vertex 0 sends one edge to 1 and receives one from 1.



S03 · impliesBefore

v=1

After

d^+(1)=2,\quad d^-(1)=1

Conditions: none

Rule: work · Uses: G1, S02, work

Leaf basis: work

Vertex 1 has outgoing edges to 0,2 and only the incoming edge from 0.



S04 · impliesBefore

v=2

After

d^+(2)=0,\quad d^-(2)=1

Conditions: none

Rule: work · Uses: G1, S03, work

Leaf basis: work

Vertex 2 has no outgoing edge and receives one from 1.



S05 · impliesBefore

\sum_vd^+(v),\quad\sum_vd^-(v)

After

1+2+0=3=|E|,\quad1+1+1=3=|E|

Conditions: none

Rule: work · Uses: G1, S04, work

Leaf basis: work

Each ordered edge contributes once to each degree sum.



S06 · impliesBefore

W=(0,1,2)

After

(0,1)\in E,\quad(1,2)\in E

Conditions: none

Rule: work · Uses: G1, S05, work

Leaf basis: work

Both steps follow the declared orientation, so W is a directed walk.



S07 · impliesBefore

W'=(2,1,0)

After

(2,1)\notin E\implies W'\text{ invalid}

Conditions: none

Rule: work · Uses: G1, S06, work

Leaf basis: work

The first reversed step lacks the required orientation, giving an explicit counterexample edge.



S08 · impliesBefore

(1,1)\text{ proposed addition}

After

u=v\implies\text{rejected under this convention}

Conditions: none

Rule: work · Uses: G1, S07, work

Leaf basis: work

A loop violates this declared model, not every possible digraph convention.







## Substeps and lemmas

No substeps in this guide.





## Reverse audits


- S08 · premise_audit · G1, S07, work — Adding a duplicate(0,1) also violates the simple-set model.
- S07 · premise_audit · G1, S06, work — Existence of(1,2) does not supply(2,1).
- S06 · premise_audit · G1, S05, work — Undirected adjacency would not suffice.
- S05 · premise_audit · G1, S04, work — One sum is not 2|E|; that combines both sums.
- S04 · premise_audit · G1, S03, work — All three vertices have been classified.
- S03 · premise_audit · G1, S02, work — Opposite edges do not cancel.
- S02 · premise_audit · G1, S01, work — Count incoming and outgoing edges separately.
- S01 · premise_audit · G1, work — (0,1) and(1,0) are not duplicates.





## Error controls and negative controls

OrientationCheck each ordered pair itself, not its unordered version.

Complete degreesList both degrees at all three vertices before summing separately.


- (0,1) and(1,0) are the same edge. → reject — Their ordered-pair orientations differ.
- The out-degree sum is 6. → reject — It is 3=|E|, not 2|E|.
- W' is valid because it reverses W. → reject — (2,1) is absent from E.





## Result and limitations

Out-degrees are(1,2,0), in-degrees(1,1,1), each summing to 3; W is valid and W' is not.







## Verification and source binding

2 declared checks for this guide; only the listed expressions are covered.


- source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
- adopted source SHA-256: 29de68530ae033900877a5ed071984a0b1139166bdb2f8540730b83646126993
- original source SHA-256: e9c6f110a34b506927711f1056970b7cb9f9b0ad5005a7b6dd237f108c5bb012
- Lean: NOT_RUN · independent AI: SCOPED_LEAD_AND_BILINGUAL_CONTEXT_REVIEW

[Same-source full JSON (formulas, ASTs, controls and revision log)](https://ocme.evemisslab.com/data/derivations/coverage-20261021/guides/derivation-mko-finite-directed-graph-01.json)