# Checking every edge and internal vertex of a feasible flow

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

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-flow-network-01 · ocme-new142-reader-adoption-20261021



## Goal and scope

Audit a complete flow network with antiparallel edges, a zero-capacity edge and a zero-flow vertex.

Only network qualification, capacity, conservation and flow value; feasibility alone does not establish maximum flow.





## Givens and symbols


- algebra
- sets
- flow_def


- G1 — V={s,a,b,t,z}, source s and distinct sink t; ordered edges sa,sb,ab,at,bt,ba,za have capacities (3,2,1,2,3,1,0) and flows (2,1,1,1,2,0,0). z has no edge except zero-capacity za.


- f_e,c_e — flow and capacity per directed edge
- |f| — net flow value





## Rules and sources


- mko_definition · cited — Use a finite loop-free simple directed graph with distinct source s and sink t. Antiparallel edges are allowed, but each ordered pair appears at most once. Valid capacities/flows are exact nonnegative rationals. Feasibility requires0≤f(e)≤c(e) and complete inflow=outflow at every internal vertex. Cross-check source net outflow against sink net inflow. Zero capacities and disconnected vertices are legal. Feasibility is not maximum flow; no min-cut equality or augmenting-path optimality is claimed ahead of its theorem. · mko-finite-flow-network
- algebra · prerequisite — Use real-field identities; division requires a nonzero denominator and multiplication by a positive number preserves inequalities.
- sets · prerequisite — Compute unions, intersections, complements, inclusion and preimages element by element.
- flow_def · prerequisite — A finite simple directed network has no self-loop or duplicate ordered pair, but permits antiparallel edges; feasible flows satisfy every capacity bound and internal conservation, with value equal to source net outflow and sink net inflow.





## Main derivation

S01 · impliesBefore

E=\{(s,a),(s,b),(a,b),(a,t),(b,t),(b,a),(z,a)\}

After

|E|=7,\quad u\ne v\text{ and each ordered pair occurs once}

Conditions: none

Rule: flow_def · Uses: G1

Leaf basis: flow_def

Each edge has endpoints in V, no loop and no duplicate ordered pair; ab and ba are legal distinct edges.



S02 · impliesBefore

(f_e,c_e)= (2,3),(1,2),(1,1),(1,2),(2,3),(0,1),(0,0)

After

0\le f_e\le c_e\quad\forall e\in E

Conditions: none

Rule: algebra · Uses: G1, S01

Leaf basis: algebra

Check all seven pairs for nonnegativity and capacity; the zero-capacity edge carries zero flow.



S03 · impliesBefore

\operatorname{in}(a)=f_{sa}+f_{ba}+f_{za}=2+0+0

After

\operatorname{in}(a)=2=f_{ab}+f_{at}=\operatorname{out}(a)

Conditions: none

Rule: algebra · Uses: G1

Leaf basis: algebra

List all three incoming and both outgoing edges of a.



S04 · impliesBefore

\operatorname{in}(b)=f_{sb}+f_{ab}=1+1

After

\operatorname{in}(b)=2=f_{bt}+f_{ba}=\operatorname{out}(b)

Conditions: none

Rule: algebra · Uses: G1

Leaf basis: algebra

The complete inflow and outflow of b agree.



S05 · impliesBefore

\operatorname{in}(z)=0,\quad\operatorname{out}(z)=f_{za}=0

After

\operatorname{in}(z)=\operatorname{out}(z)

Conditions: none

Rule: algebra · Uses: G1

Leaf basis: algebra

z has no inflow and its sole outgoing edge has zero capacity, so conservation holds; it is a zero-flow vertex, not an isolated graph vertex.



S06 · impliesBefore

|f|=\operatorname{out}(s)-\operatorname{in}(s)=2+1-0

After

|f|=3=\operatorname{in}(t)-\operatorname{out}(t)=1+2-0

Conditions: none

Rule: algebra · Uses: G1, S03, S04, S05

Leaf basis: algebra

Source and sink net values independently evaluate to the same result.



S07 · definitionBefore

0\le f\le c,\quad\operatorname{in}=\operatorname{out}\text{ at }a,b,z

After

f\text{ is feasible with value }3

Conditions: none

Rule: flow_def · Uses: S01, S02, S03, S04, S05, S06

Leaf basis: flow_def

Only after all edges and internal vertices are checked is feasibility concluded.



S08 · impliesBefore

f'=(3,1,1,2,2,0,0)\text{ in the same edge order}

After

f'\text{ is feasible with }|f'|=4>3

Conditions: none

Rule: algebra · Uses: G1, S07

Leaf basis: algebra

The alternative satisfies every capacity; a has 3 in and 1+2 out, b has 1+1 in and 2 out, and z stays zero, proving the original is not maximum.







## Substeps and lemmas

No substeps in this guide.





## Reverse audits


- S08 · premise_audit · G1, S07 — A larger feasible flow refutes maximum-value optimality without invoking the min-cut theorem.
- S07 · premise_audit · S01, S02, S03, S04, S05, S06 — No optimality certificate has been supplied, so it is not called maximum.
- S06 · premise_audit · G1, S03, S04, S05 — Net values subtract reverse-direction flow; this graph has no source in-edge or sink out-edge, so these are zero.
- S05 · premise_audit · G1 — A zero-capacity edge remains a graph edge: z→a→t is a graph path but carries no positive flow because of the zero capacity; z is not isolated.
- S04 · premise_audit · G1 — ab is incoming at b and outgoing at a.
- S03 · premise_audit · G1 — Do not omit ba or za merely because their flows are zero.
- S02 · premise_audit · G1, S01 — A small total value does not imply edge legality; each edge is separately checked.
- S01 · premise_audit · G1 — Antiparallel is not duplicate; both capacity and flow keys match all seven edges.





## Error controls and negative controls

Complete key correspondenceCapacity and flow keys may neither omit nor add edges.

Net-value cross-checkCompute both s and t independently.


- Having both ab and ba is illegal. → reject — A simple directed graph forbids duplicate ordered pairs, not antiparallel edges.
- The source value alone proves feasibility. → reject — Every edge and internal vertex still requires auditing.
- Feasible means maximum. → reject — S08 gives a larger feasible flow.





## Result and limitations

The original flow is feasible with value 3; a value-4 feasible flow proves it is not maximum.







## Verification and source binding

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


- source commit: b1b2f1dcf8c50d67a93fe52d95f8eef7b3abba9f
- adopted source SHA-256: a93c0418ecb143d4880146293689ec4965fd3d889bdf228e7d45a98a09ddfb2c
- original source SHA-256: 9ddde2b86d73fa9084b762788ec009ac727c1ea81b32343655d29131ebaa1df4
- 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-flow-network-01.json)