Solved at Scale
Cross-Checking with the Cut
A solver flow becomes a certificate when independent computations agree. This repo's own arithmetic re-verifies feasibility, its own Ford-Fulkerson reaches the same value on the same network, and that run's own min cut matches — the book's theorem holding on real data.
Independent re-verification
This repo's own exact integer arithmetic re-checks the decoded flow at every build: every arc's flow stays within its capacity, conservation holds at all 3 middle nodes, and the flow out of the source equals the reported total and the flow into the sink. Why: an independent check must not reuse the solver's code path, and any violation would stop the build rather than let a wrong flow through.
The book's own Ford-Fulkerson
This book's own Ford-Fulkerson runs live on the same instance and reaches 60. One honest preprocessing note: the teaching algorithm does not accept anti-parallel arcs, so the arc N4 to N3 was split through one dummy node D1 — a standard value-preserving transformation giving 6 nodes and 10 arcs. The two assignments coincide on this instance, and the value is the certificate: max-flow assignments can be non-unique in general, so agreement of the flows themselves is not required, only agreement of the value.
The cut agrees
That same own run's min cut is the three source arcs, with capacities 20 + 30 + 10 = 60, exactly the flow value. Why: any feasible flow is at most any cut's capacity, so a flow and a cut that reach the same number close the gap from both sides at once — the flow proves at least that much is achievable, the cut proves no more than that much ever could be, and the two together are checkable by anyone who can add three capacities, with no need to trust either algorithm.
Diagram note
The diagram is the split network, honestly labeled: nodes N1 through N5 plus the dummy D1; the cut marking is recomputed by the atom from its own run. Pixel positions are rounded for layout; every number shown is exact.