# Question 25948: An Equal-Valued Feasible Flow and Cut Certify Both Optima

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

[← Question derivation index](https://ocme.evemisslab.com/en/questions/) · [Original question batch](https://ocme.evemisslab.com/en/practice/batch-20261015-advance-20261115-r05-max-flow-min-cut-theorem-foundations/#q-20261015-advance-20261115-r05-max-flow-min-cut-theorem-0098)

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.

R0050-25948 · q-20261015-advance-20261115-r05-max-flow-min-cut-theorem-0098



## Original question and givens

Use complete directed vertices=[s, a0, a1, a2, a3, t], ordered edges=[[s, a0], [a0, t], [s, a1], [a1, t], [s, a2], [a2, t], [s, a3], [a3, t]], source=s, sink=t, aligned nonnegative exact capacities=[24, 24, 25, 25, 26, 26, 27, 27], candidate flows=[24, 24, 25, 25, 26, 26, 27, 27]. A cut contains the source and excludes the sink; its capacity sums only edges leaving the cut, not incoming edges. Give (flow_value, minimum_capacity, equal_value_cuts, minimum_cuts, equal_values, maximum_flow_certificate, minimum_cut_certificate, integrality_or_algorithm_claim, certificate).


- G001 — Use complete directed vertices=[s, a0, a1, a2, a3, t], ordered edges=[[s, a0], [a0, t], [s, a1], [a1, t], [s, a2], [a2, t], [s, a3], [a3, t]], source=s, sink=t, aligned nonnegative exact capacities=[24, 24, 25, 25, 26, 26, 27, 27], candidate flows=[24, 24, 25, 25, 26, 26, 27, 27]. A cut contains the source and excludes the sink; its capacity sums only edges leaving the cut, not incoming edges. Give (flow_value, minimum_capacity, equal_value_cuts, minimum_cuts, equal_values, maximum_flow_certificate, minimum_cut_certificate, integrality_or_algorithm_claim, certificate).





## Definition and scope

Use the original question domain, assumptions and cited MKO definitions. This item has second-context mathematical and bilingual review, with the model, answer and every arithmetic step independently recomputed from the original parameters; the source question remains a candidate.


- [mko-max-flow-min-cut-theorem](https://ocme.evemisslab.com/en/mko/mko-max-flow-min-cut-theorem/)





## Step-by-step derivation

S001 · impliesBefore

source roles = [mfmc-equal-value-optimality]

After

derived = [[flow_value, minimum_capacity, equal_value_cuts, minimum_cuts, equal_values, maximum_flow_certificate, minimum_cut_certificate, integrality_or_algorithm_claim, certificate]]

Conditions: none

List the full source field order without JavaScript.LP weak uses13 fields,zero/strong15;premises and roles follow the original operation/mode without padding.

Step identifiers and dependenciesRule: source_ordered_fields_without_JS · Uses: G001





S002 · impliesBefore

source roles = [[s, a0, a1, a2, a3, t], [[s, a0], [a0, t], [s, a1], [a1, t], [s, a2], [a2, t], [s, a3], [a3, t]], [24, 24, 25, 25, 26, 26, 27, 27], [24, 24, 25, 25, 26, 26, 27, 27], s, t]

After

derived = [[a0, a1, a2, a3, s, t], [[a0, t], [a1, t], [a2, t], [a3, t], [s, a0], [s, a1], [s, a2], [s, a3]], [24, 25, 26, 27, 24, 25, 26, 27], [24, 25, 26, 27, 24, 25, 26, 27]]

Conditions: none

Use2..12 vertices.Zip directed edges with capacity/flow by original index before sorting;reverse arcs remain distinct.Source and sink differ;reject loops/duplicates but allow zero capacities,no edges and isolated vertices.

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





S003 · calculationBefore

MFMC cut mask0 OUTWARD capacity := sum(24, 25, 26, 27)

After

MFMC cut mask0 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

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





S004 · impliesBefore

source roles = [0, [a0, a1, a2, a3], [s]]

After

derived = [[4, 5, 6, 7], [], [[[s, a0], 24], [[s, a1], 25], [[s, a2], 26], [[s, a3], 27]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

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





S005 · calculationBefore

MFMC cut mask1 OUTWARD capacity := sum(24, 25, 26, 27)

After

MFMC cut mask1 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

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





S006 · impliesBefore

source roles = [1, [a0, a1, a2, a3], [a0, s]]

After

derived = [[0, 5, 6, 7], [], [[[a0, t], 24], [[s, a1], 25], [[s, a2], 26], [[s, a3], 27]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

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





S007 · calculationBefore

MFMC cut mask2 OUTWARD capacity := sum(25, 24, 26, 27)

After

MFMC cut mask2 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

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





S008 · impliesBefore

source roles = [2, [a0, a1, a2, a3], [a1, s]]

After

derived = [[1, 4, 6, 7], [], [[[a1, t], 25], [[s, a0], 24], [[s, a2], 26], [[s, a3], 27]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

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





S009 · calculationBefore

MFMC cut mask3 OUTWARD capacity := sum(24, 25, 26, 27)

After

MFMC cut mask3 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

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





S010 · impliesBefore

source roles = [3, [a0, a1, a2, a3], [a0, a1, s]]

After

derived = [[0, 1, 6, 7], [], [[[a0, t], 24], [[a1, t], 25], [[s, a2], 26], [[s, a3], 27]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S009





S011 · calculationBefore

MFMC cut mask4 OUTWARD capacity := sum(26, 24, 25, 27)

After

MFMC cut mask4 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S010





S012 · impliesBefore

source roles = [4, [a0, a1, a2, a3], [a2, s]]

After

derived = [[2, 4, 5, 7], [], [[[a2, t], 26], [[s, a0], 24], [[s, a1], 25], [[s, a3], 27]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S011





S013 · calculationBefore

MFMC cut mask5 OUTWARD capacity := sum(24, 26, 25, 27)

After

MFMC cut mask5 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S012





S014 · impliesBefore

source roles = [5, [a0, a1, a2, a3], [a0, a2, s]]

After

derived = [[0, 2, 5, 7], [], [[[a0, t], 24], [[a2, t], 26], [[s, a1], 25], [[s, a3], 27]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S013





S015 · calculationBefore

MFMC cut mask6 OUTWARD capacity := sum(25, 26, 24, 27)

After

MFMC cut mask6 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S014





S016 · impliesBefore

source roles = [6, [a0, a1, a2, a3], [a1, a2, s]]

After

derived = [[1, 2, 4, 7], [], [[[a1, t], 25], [[a2, t], 26], [[s, a0], 24], [[s, a3], 27]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S015





S017 · calculationBefore

MFMC cut mask7 OUTWARD capacity := sum(24, 25, 26, 27)

After

MFMC cut mask7 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S016





S018 · impliesBefore

source roles = [7, [a0, a1, a2, a3], [a0, a1, a2, s]]

After

derived = [[0, 1, 2, 7], [], [[[a0, t], 24], [[a1, t], 25], [[a2, t], 26], [[s, a3], 27]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S017





S019 · calculationBefore

MFMC cut mask8 OUTWARD capacity := sum(27, 24, 25, 26)

After

MFMC cut mask8 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S018





S020 · impliesBefore

source roles = [8, [a0, a1, a2, a3], [a3, s]]

After

derived = [[3, 4, 5, 6], [], [[[a3, t], 27], [[s, a0], 24], [[s, a1], 25], [[s, a2], 26]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S019





S021 · calculationBefore

MFMC cut mask9 OUTWARD capacity := sum(24, 27, 25, 26)

After

MFMC cut mask9 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S020





S022 · impliesBefore

source roles = [9, [a0, a1, a2, a3], [a0, a3, s]]

After

derived = [[0, 3, 5, 6], [], [[[a0, t], 24], [[a3, t], 27], [[s, a1], 25], [[s, a2], 26]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S021





S023 · calculationBefore

MFMC cut mask10 OUTWARD capacity := sum(25, 27, 24, 26)

After

MFMC cut mask10 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S022





S024 · impliesBefore

source roles = [10, [a0, a1, a2, a3], [a1, a3, s]]

After

derived = [[1, 3, 4, 6], [], [[[a1, t], 25], [[a3, t], 27], [[s, a0], 24], [[s, a2], 26]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S023





S025 · calculationBefore

MFMC cut mask11 OUTWARD capacity := sum(24, 25, 27, 26)

After

MFMC cut mask11 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S024





S026 · impliesBefore

source roles = [11, [a0, a1, a2, a3], [a0, a1, a3, s]]

After

derived = [[0, 1, 3, 6], [], [[[a0, t], 24], [[a1, t], 25], [[a3, t], 27], [[s, a2], 26]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S025





S027 · calculationBefore

MFMC cut mask12 OUTWARD capacity := sum(26, 27, 24, 25)

After

MFMC cut mask12 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S026





S028 · impliesBefore

source roles = [12, [a0, a1, a2, a3], [a2, a3, s]]

After

derived = [[2, 3, 4, 5], [], [[[a2, t], 26], [[a3, t], 27], [[s, a0], 24], [[s, a1], 25]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S027





S029 · calculationBefore

MFMC cut mask13 OUTWARD capacity := sum(24, 26, 27, 25)

After

MFMC cut mask13 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S028





S030 · impliesBefore

source roles = [13, [a0, a1, a2, a3], [a0, a2, a3, s]]

After

derived = [[0, 2, 3, 5], [], [[[a0, t], 24], [[a2, t], 26], [[a3, t], 27], [[s, a1], 25]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S029





S031 · calculationBefore

MFMC cut mask14 OUTWARD capacity := sum(25, 26, 27, 24)

After

MFMC cut mask14 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S030





S032 · impliesBefore

source roles = [14, [a0, a1, a2, a3], [a1, a2, a3, s]]

After

derived = [[1, 2, 3, 4], [], [[[a1, t], 25], [[a2, t], 26], [[a3, t], 27], [[s, a0], 24]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S031





S033 · calculationBefore

MFMC cut mask15 OUTWARD capacity := sum(24, 25, 26, 27)

After

MFMC cut mask15 OUTWARD capacity = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S032





S034 · impliesBefore

source roles = [15, [a0, a1, a2, a3], [a0, a1, a2, a3, s]]

After

derived = [[0, 1, 2, 3], [], [[[a0, t], 24], [[a1, t], 25], [[a2, t], 26], [[a3, t], 27]], 102]

Conditions: none

S contains source and excludes sink.Enumerate every other-vertex subset;sort inside S by UTF16 but retain numeric-mask outer order.Capacity sums OUTWARD edges only,not incoming edges;ties are not re-sorted in English.

Step identifiers and dependenciesRule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S033





S035 · impliesBefore

source roles = [[a0, a1, a2, a3, s, t], [a0, a1, a2, a3]]

After

derived = [16, 16, 102, [[s], [a0, s], [a1, s], [a0, a1, s], [a2, s], [a0, a2, s], [a1, a2, s], [a0, a1, a2, s], [a3, s], [a0, a3, s], [a1, a3, s], [a0, a1, a3, s], [a2, a3, s], [a0, a2, a3, s], [a1, a2, a3, s], [a0, a1, a2, a3, s]]]

Conditions: none

Every s–t cut uniquely corresponds to a subset of other vertices,so all2^(n−2) cuts are compared.Select the minimum and all minimizers from this same complete family,retaining mask tie order.

Step identifiers and dependenciesRule: MFMC_ALL_cut_family_complete_minimum_and_ALL_ties · Uses: G001, S034





S036 · calculationBefore

MFMC vertex a0 ALL incoming := sum(24)

After

MFMC vertex a0 ALL incoming = 24

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S035





S037 · calculationBefore

MFMC vertex a0 ALL outgoing := sum(24)

After

MFMC vertex a0 ALL outgoing = 24

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S036





S038 · calculationBefore

MFMC vertex a1 ALL incoming := sum(25)

After

MFMC vertex a1 ALL incoming = 25

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S037





S039 · calculationBefore

MFMC vertex a1 ALL outgoing := sum(25)

After

MFMC vertex a1 ALL outgoing = 25

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S038





S040 · calculationBefore

MFMC vertex a2 ALL incoming := sum(26)

After

MFMC vertex a2 ALL incoming = 26

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S039





S041 · calculationBefore

MFMC vertex a2 ALL outgoing := sum(26)

After

MFMC vertex a2 ALL outgoing = 26

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S040





S042 · calculationBefore

MFMC vertex a3 ALL incoming := sum(27)

After

MFMC vertex a3 ALL incoming = 27

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S041





S043 · calculationBefore

MFMC vertex a3 ALL outgoing := sum(27)

After

MFMC vertex a3 ALL outgoing = 27

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S042





S044 · calculationBefore

MFMC vertex s ALL incoming := sum()

After

MFMC vertex s ALL incoming = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S043





S045 · calculationBefore

MFMC vertex s ALL outgoing := sum(24, 25, 26, 27)

After

MFMC vertex s ALL outgoing = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S044





S046 · calculationBefore

MFMC vertex t ALL incoming := sum(24, 25, 26, 27)

After

MFMC vertex t ALL incoming = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S045





S047 · calculationBefore

MFMC vertex t ALL outgoing := sum()

After

MFMC vertex t ALL outgoing = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S046





S048 · calculationBefore

MFMC SOURCE net out not gross := sub(102, 0)

After

MFMC SOURCE net out not gross = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S047





S049 · calculationBefore

MFMC SINK net in not gross := sub(102, 0)

After

MFMC SINK net in not gross = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S048





S050 · impliesBefore

source roles = [[[a0, t], [a1, t], [a2, t], [a3, t], [s, a0], [s, a1], [s, a2], [s, a3]], [24, 25, 26, 27, 24, 25, 26, 27], [24, 25, 26, 27, 24, 25, 26, 27], s, t]

After

derived = [[[[a0, t], 24, 24, Yes], [[a1, t], 25, 25, Yes], [[a2, t], 26, 26, Yes], [[a3, t], 27, 27, Yes], [[s, a0], 24, 24, Yes], [[s, a1], 25, 25, Yes], [[s, a2], 26, 26, Yes], [[s, a3], 27, 27, Yes]], [[a0, 24, 24, Yes], [a1, 25, 25, Yes], [a2, 26, 26, Yes], [a3, 27, 27, Yes]], Yes, Yes, 102, 102, Yes, Yes]

Conditions: none

Feasibility requires every edge capacity bound,every internal conservation equation and equal source/sink NET values.Do not discard incoming-source or outgoing-sink arcs.A feasible flow may have negative net value;do not add value>=0.

Step identifiers and dependenciesRule: MFMC_EVERY_capacity_EVERY_internal_balance_source_sink_NET_feasibility · Uses: G001, S049





S051 · calculationBefore

MFMC cut mask0 OUTWARD flow := sum(24, 25, 26, 27)

After

MFMC cut mask0 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S050





S052 · calculationBefore

MFMC cut mask0 INWARD flow := sum()

After

MFMC cut mask0 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S051





S053 · calculationBefore

MFMC cut mask0 NET flow := sub(102, 0)

After

MFMC cut mask0 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S052





S054 · impliesBefore

source roles = [[s], [4, 5, 6, 7], [], 102]

After

derived = [[[s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S053





S055 · calculationBefore

MFMC cut mask1 OUTWARD flow := sum(24, 25, 26, 27)

After

MFMC cut mask1 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S054





S056 · calculationBefore

MFMC cut mask1 INWARD flow := sum()

After

MFMC cut mask1 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S055





S057 · calculationBefore

MFMC cut mask1 NET flow := sub(102, 0)

After

MFMC cut mask1 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S056





S058 · impliesBefore

source roles = [[a0, s], [0, 5, 6, 7], [], 102]

After

derived = [[[a0, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S057





S059 · calculationBefore

MFMC cut mask2 OUTWARD flow := sum(25, 24, 26, 27)

After

MFMC cut mask2 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S058





S060 · calculationBefore

MFMC cut mask2 INWARD flow := sum()

After

MFMC cut mask2 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S059





S061 · calculationBefore

MFMC cut mask2 NET flow := sub(102, 0)

After

MFMC cut mask2 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S060





S062 · impliesBefore

source roles = [[a1, s], [1, 4, 6, 7], [], 102]

After

derived = [[[a1, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S061





S063 · calculationBefore

MFMC cut mask3 OUTWARD flow := sum(24, 25, 26, 27)

After

MFMC cut mask3 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S062





S064 · calculationBefore

MFMC cut mask3 INWARD flow := sum()

After

MFMC cut mask3 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S063





S065 · calculationBefore

MFMC cut mask3 NET flow := sub(102, 0)

After

MFMC cut mask3 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S064





S066 · impliesBefore

source roles = [[a0, a1, s], [0, 1, 6, 7], [], 102]

After

derived = [[[a0, a1, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S065





S067 · calculationBefore

MFMC cut mask4 OUTWARD flow := sum(26, 24, 25, 27)

After

MFMC cut mask4 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S066





S068 · calculationBefore

MFMC cut mask4 INWARD flow := sum()

After

MFMC cut mask4 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S067





S069 · calculationBefore

MFMC cut mask4 NET flow := sub(102, 0)

After

MFMC cut mask4 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S068





S070 · impliesBefore

source roles = [[a2, s], [2, 4, 5, 7], [], 102]

After

derived = [[[a2, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S069





S071 · calculationBefore

MFMC cut mask5 OUTWARD flow := sum(24, 26, 25, 27)

After

MFMC cut mask5 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S070





S072 · calculationBefore

MFMC cut mask5 INWARD flow := sum()

After

MFMC cut mask5 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S071





S073 · calculationBefore

MFMC cut mask5 NET flow := sub(102, 0)

After

MFMC cut mask5 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S072





S074 · impliesBefore

source roles = [[a0, a2, s], [0, 2, 5, 7], [], 102]

After

derived = [[[a0, a2, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S073





S075 · calculationBefore

MFMC cut mask6 OUTWARD flow := sum(25, 26, 24, 27)

After

MFMC cut mask6 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S074





S076 · calculationBefore

MFMC cut mask6 INWARD flow := sum()

After

MFMC cut mask6 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S075





S077 · calculationBefore

MFMC cut mask6 NET flow := sub(102, 0)

After

MFMC cut mask6 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S076





S078 · impliesBefore

source roles = [[a1, a2, s], [1, 2, 4, 7], [], 102]

After

derived = [[[a1, a2, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S077





S079 · calculationBefore

MFMC cut mask7 OUTWARD flow := sum(24, 25, 26, 27)

After

MFMC cut mask7 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S078





S080 · calculationBefore

MFMC cut mask7 INWARD flow := sum()

After

MFMC cut mask7 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S079





S081 · calculationBefore

MFMC cut mask7 NET flow := sub(102, 0)

After

MFMC cut mask7 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S080





S082 · impliesBefore

source roles = [[a0, a1, a2, s], [0, 1, 2, 7], [], 102]

After

derived = [[[a0, a1, a2, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S081





S083 · calculationBefore

MFMC cut mask8 OUTWARD flow := sum(27, 24, 25, 26)

After

MFMC cut mask8 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S082





S084 · calculationBefore

MFMC cut mask8 INWARD flow := sum()

After

MFMC cut mask8 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S083





S085 · calculationBefore

MFMC cut mask8 NET flow := sub(102, 0)

After

MFMC cut mask8 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S084





S086 · impliesBefore

source roles = [[a3, s], [3, 4, 5, 6], [], 102]

After

derived = [[[a3, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S085





S087 · calculationBefore

MFMC cut mask9 OUTWARD flow := sum(24, 27, 25, 26)

After

MFMC cut mask9 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S086





S088 · calculationBefore

MFMC cut mask9 INWARD flow := sum()

After

MFMC cut mask9 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S087





S089 · calculationBefore

MFMC cut mask9 NET flow := sub(102, 0)

After

MFMC cut mask9 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S088





S090 · impliesBefore

source roles = [[a0, a3, s], [0, 3, 5, 6], [], 102]

After

derived = [[[a0, a3, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S089





S091 · calculationBefore

MFMC cut mask10 OUTWARD flow := sum(25, 27, 24, 26)

After

MFMC cut mask10 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S090





S092 · calculationBefore

MFMC cut mask10 INWARD flow := sum()

After

MFMC cut mask10 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S091





S093 · calculationBefore

MFMC cut mask10 NET flow := sub(102, 0)

After

MFMC cut mask10 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S092





S094 · impliesBefore

source roles = [[a1, a3, s], [1, 3, 4, 6], [], 102]

After

derived = [[[a1, a3, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S093





S095 · calculationBefore

MFMC cut mask11 OUTWARD flow := sum(24, 25, 27, 26)

After

MFMC cut mask11 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S094





S096 · calculationBefore

MFMC cut mask11 INWARD flow := sum()

After

MFMC cut mask11 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S095





S097 · calculationBefore

MFMC cut mask11 NET flow := sub(102, 0)

After

MFMC cut mask11 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S096





S098 · impliesBefore

source roles = [[a0, a1, a3, s], [0, 1, 3, 6], [], 102]

After

derived = [[[a0, a1, a3, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S097





S099 · calculationBefore

MFMC cut mask12 OUTWARD flow := sum(26, 27, 24, 25)

After

MFMC cut mask12 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S098





S100 · calculationBefore

MFMC cut mask12 INWARD flow := sum()

After

MFMC cut mask12 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S099





S101 · calculationBefore

MFMC cut mask12 NET flow := sub(102, 0)

After

MFMC cut mask12 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S100





S102 · impliesBefore

source roles = [[a2, a3, s], [2, 3, 4, 5], [], 102]

After

derived = [[[a2, a3, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S101





S103 · calculationBefore

MFMC cut mask13 OUTWARD flow := sum(24, 26, 27, 25)

After

MFMC cut mask13 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S102





S104 · calculationBefore

MFMC cut mask13 INWARD flow := sum()

After

MFMC cut mask13 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S103





S105 · calculationBefore

MFMC cut mask13 NET flow := sub(102, 0)

After

MFMC cut mask13 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S104





S106 · impliesBefore

source roles = [[a0, a2, a3, s], [0, 2, 3, 5], [], 102]

After

derived = [[[a0, a2, a3, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S105





S107 · calculationBefore

MFMC cut mask14 OUTWARD flow := sum(25, 26, 27, 24)

After

MFMC cut mask14 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S106





S108 · calculationBefore

MFMC cut mask14 INWARD flow := sum()

After

MFMC cut mask14 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S107





S109 · calculationBefore

MFMC cut mask14 NET flow := sub(102, 0)

After

MFMC cut mask14 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S108





S110 · impliesBefore

source roles = [[a1, a2, a3, s], [1, 2, 3, 4], [], 102]

After

derived = [[[a1, a2, a3, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S109





S111 · calculationBefore

MFMC cut mask15 OUTWARD flow := sum(24, 25, 26, 27)

After

MFMC cut mask15 OUTWARD flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S110





S112 · calculationBefore

MFMC cut mask15 INWARD flow := sum()

After

MFMC cut mask15 INWARD flow = 0

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S111





S113 · calculationBefore

MFMC cut mask15 NET flow := sub(102, 0)

After

MFMC cut mask15 NET flow = 102

Conditions: none

Substitute original roles and established intermediates exactly,without floats;extra teaching identities do not impose new source numeric restrictions.

Step identifiers and dependenciesRule: exact_rational_arithmetic · Uses: G001, S112





S114 · impliesBefore

source roles = [[a0, a1, a2, a3, s], [0, 1, 2, 3], [], 102]

After

derived = [[[a0, a1, a2, a3, s], 102, 0, 102, 102, Yes, Yes]]

Conditions: none

Summing net outflows over S cancels internal arcs;internal conservation leaves the source net.Because inward flow is nonnegative and each outward flow is capacity-bounded,value=out−in<=out<=cut capacity,for every cut.

Step identifiers and dependenciesRule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S113





S115 · impliesBefore

source roles = [Yes, 102, 102, [[s], [a0, s], [a1, s], [a0, a1, s], [a2, s], [a0, a2, s], [a1, a2, s], [a0, a1, a2, s], [a3, s], [a0, a3, s], [a1, a3, s], [a0, a1, a3, s], [a2, a3, s], [a0, a2, a3, s], [a1, a2, a3, s], [a0, a1, a2, a3, s]]]

After

derived = [[[s], [a0, s], [a1, s], [a0, a1, s], [a2, s], [a0, a2, s], [a1, a2, s], [a0, a1, a2, s], [a3, s], [a0, a3, s], [a1, a3, s], [a0, a1, a3, s], [a2, a3, s], [a0, a2, a3, s], [a1, a2, a3, s], [a0, a1, a2, a3, s]], Yes, Yes, Yes, No]

Conditions: none

Any feasible flow is bounded by this equal-valued cut,and any cut is bounded below by this feasible flow,so the current flow is maximum and equal-valued cuts minimum.This uses universal weak bounds plus feasibility,not bare equality.The final No only withholds integrality/algorithm proof.

Step identifiers and dependenciesRule: MFMC_feasible_equal_value_GENERAL_bounds_certify_BOTH_optima · Uses: G001, S114









## Reverse checks


- S115 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S114 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S113 · premise_and_result_audit — Recompute MFMC cut mask15 NET flow with exact rational arithmetic, not rounded decimals.
- S112 · premise_and_result_audit — Recompute MFMC cut mask15 INWARD flow with exact rational arithmetic, not rounded decimals.
- S111 · premise_and_result_audit — Recompute MFMC cut mask15 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S110 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S109 · premise_and_result_audit — Recompute MFMC cut mask14 NET flow with exact rational arithmetic, not rounded decimals.
- S108 · premise_and_result_audit — Recompute MFMC cut mask14 INWARD flow with exact rational arithmetic, not rounded decimals.
- S107 · premise_and_result_audit — Recompute MFMC cut mask14 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S106 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S105 · premise_and_result_audit — Recompute MFMC cut mask13 NET flow with exact rational arithmetic, not rounded decimals.
- S104 · premise_and_result_audit — Recompute MFMC cut mask13 INWARD flow with exact rational arithmetic, not rounded decimals.
- S103 · premise_and_result_audit — Recompute MFMC cut mask13 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S102 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S101 · premise_and_result_audit — Recompute MFMC cut mask12 NET flow with exact rational arithmetic, not rounded decimals.
- S100 · premise_and_result_audit — Recompute MFMC cut mask12 INWARD flow with exact rational arithmetic, not rounded decimals.
- S099 · premise_and_result_audit — Recompute MFMC cut mask12 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S098 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S097 · premise_and_result_audit — Recompute MFMC cut mask11 NET flow with exact rational arithmetic, not rounded decimals.
- S096 · premise_and_result_audit — Recompute MFMC cut mask11 INWARD flow with exact rational arithmetic, not rounded decimals.
- S095 · premise_and_result_audit — Recompute MFMC cut mask11 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S094 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S093 · premise_and_result_audit — Recompute MFMC cut mask10 NET flow with exact rational arithmetic, not rounded decimals.
- S092 · premise_and_result_audit — Recompute MFMC cut mask10 INWARD flow with exact rational arithmetic, not rounded decimals.
- S091 · premise_and_result_audit — Recompute MFMC cut mask10 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S090 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S089 · premise_and_result_audit — Recompute MFMC cut mask9 NET flow with exact rational arithmetic, not rounded decimals.
- S088 · premise_and_result_audit — Recompute MFMC cut mask9 INWARD flow with exact rational arithmetic, not rounded decimals.
- S087 · premise_and_result_audit — Recompute MFMC cut mask9 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S086 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S085 · premise_and_result_audit — Recompute MFMC cut mask8 NET flow with exact rational arithmetic, not rounded decimals.
- S084 · premise_and_result_audit — Recompute MFMC cut mask8 INWARD flow with exact rational arithmetic, not rounded decimals.
- S083 · premise_and_result_audit — Recompute MFMC cut mask8 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S082 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S081 · premise_and_result_audit — Recompute MFMC cut mask7 NET flow with exact rational arithmetic, not rounded decimals.
- S080 · premise_and_result_audit — Recompute MFMC cut mask7 INWARD flow with exact rational arithmetic, not rounded decimals.
- S079 · premise_and_result_audit — Recompute MFMC cut mask7 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S078 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S077 · premise_and_result_audit — Recompute MFMC cut mask6 NET flow with exact rational arithmetic, not rounded decimals.
- S076 · premise_and_result_audit — Recompute MFMC cut mask6 INWARD flow with exact rational arithmetic, not rounded decimals.
- S075 · premise_and_result_audit — Recompute MFMC cut mask6 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S074 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S073 · premise_and_result_audit — Recompute MFMC cut mask5 NET flow with exact rational arithmetic, not rounded decimals.
- S072 · premise_and_result_audit — Recompute MFMC cut mask5 INWARD flow with exact rational arithmetic, not rounded decimals.
- S071 · premise_and_result_audit — Recompute MFMC cut mask5 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S070 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S069 · premise_and_result_audit — Recompute MFMC cut mask4 NET flow with exact rational arithmetic, not rounded decimals.
- S068 · premise_and_result_audit — Recompute MFMC cut mask4 INWARD flow with exact rational arithmetic, not rounded decimals.
- S067 · premise_and_result_audit — Recompute MFMC cut mask4 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S066 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S065 · premise_and_result_audit — Recompute MFMC cut mask3 NET flow with exact rational arithmetic, not rounded decimals.
- S064 · premise_and_result_audit — Recompute MFMC cut mask3 INWARD flow with exact rational arithmetic, not rounded decimals.
- S063 · premise_and_result_audit — Recompute MFMC cut mask3 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S062 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S061 · premise_and_result_audit — Recompute MFMC cut mask2 NET flow with exact rational arithmetic, not rounded decimals.
- S060 · premise_and_result_audit — Recompute MFMC cut mask2 INWARD flow with exact rational arithmetic, not rounded decimals.
- S059 · premise_and_result_audit — Recompute MFMC cut mask2 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S058 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S057 · premise_and_result_audit — Recompute MFMC cut mask1 NET flow with exact rational arithmetic, not rounded decimals.
- S056 · premise_and_result_audit — Recompute MFMC cut mask1 INWARD flow with exact rational arithmetic, not rounded decimals.
- S055 · premise_and_result_audit — Recompute MFMC cut mask1 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S054 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S053 · premise_and_result_audit — Recompute MFMC cut mask0 NET flow with exact rational arithmetic, not rounded decimals.
- S052 · premise_and_result_audit — Recompute MFMC cut mask0 INWARD flow with exact rational arithmetic, not rounded decimals.
- S051 · premise_and_result_audit — Recompute MFMC cut mask0 OUTWARD flow with exact rational arithmetic, not rounded decimals.
- S050 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S049 · premise_and_result_audit — Recompute MFMC SINK net in not gross with exact rational arithmetic, not rounded decimals.
- S048 · premise_and_result_audit — Recompute MFMC SOURCE net out not gross with exact rational arithmetic, not rounded decimals.
- S047 · premise_and_result_audit — Recompute MFMC vertex t ALL outgoing with exact rational arithmetic, not rounded decimals.
- S046 · premise_and_result_audit — Recompute MFMC vertex t ALL incoming with exact rational arithmetic, not rounded decimals.
- S045 · premise_and_result_audit — Recompute MFMC vertex s ALL outgoing with exact rational arithmetic, not rounded decimals.
- S044 · premise_and_result_audit — Recompute MFMC vertex s ALL incoming with exact rational arithmetic, not rounded decimals.
- S043 · premise_and_result_audit — Recompute MFMC vertex a3 ALL outgoing with exact rational arithmetic, not rounded decimals.
- S042 · premise_and_result_audit — Recompute MFMC vertex a3 ALL incoming with exact rational arithmetic, not rounded decimals.
- S041 · premise_and_result_audit — Recompute MFMC vertex a2 ALL outgoing with exact rational arithmetic, not rounded decimals.
- S040 · premise_and_result_audit — Recompute MFMC vertex a2 ALL incoming with exact rational arithmetic, not rounded decimals.
- S039 · premise_and_result_audit — Recompute MFMC vertex a1 ALL outgoing with exact rational arithmetic, not rounded decimals.
- S038 · premise_and_result_audit — Recompute MFMC vertex a1 ALL incoming with exact rational arithmetic, not rounded decimals.
- S037 · premise_and_result_audit — Recompute MFMC vertex a0 ALL outgoing with exact rational arithmetic, not rounded decimals.
- S036 · premise_and_result_audit — Recompute MFMC vertex a0 ALL incoming with exact rational arithmetic, not rounded decimals.
- S035 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S034 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S033 · premise_and_result_audit — Recompute MFMC cut mask15 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S032 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S031 · premise_and_result_audit — Recompute MFMC cut mask14 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S030 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S029 · premise_and_result_audit — Recompute MFMC cut mask13 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S028 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S027 · premise_and_result_audit — Recompute MFMC cut mask12 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S026 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S025 · premise_and_result_audit — Recompute MFMC cut mask11 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S024 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S023 · premise_and_result_audit — Recompute MFMC cut mask10 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S022 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S021 · premise_and_result_audit — Recompute MFMC cut mask9 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S020 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S019 · premise_and_result_audit — Recompute MFMC cut mask8 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S018 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S017 · premise_and_result_audit — Recompute MFMC cut mask7 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S016 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S015 · premise_and_result_audit — Recompute MFMC cut mask6 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S014 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S013 · premise_and_result_audit — Recompute MFMC cut mask5 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S012 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S011 · premise_and_result_audit — Recompute MFMC cut mask4 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S010 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S009 · premise_and_result_audit — Recompute MFMC cut mask3 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S008 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S007 · premise_and_result_audit — Recompute MFMC cut mask2 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S006 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S005 · premise_and_result_audit — Recompute MFMC cut mask1 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S004 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S003 · premise_and_result_audit — Recompute MFMC cut mask0 OUTWARD capacity with exact rational arithmetic, not rounded decimals.
- S002 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
- S001 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.





## Result

(102, 102, [[s], [a0, s], [a1, s], [a0, a1, s], [a2, s], [a0, a2, s], [a1, a2, s], [a0, a1, a2, s], [a3, s], [a0, a3, s], [a1, a3, s], [a0, a1, a3, s], [a2, a3, s], [a0, a2, a3, s], [a1, a2, a3, s], [a0, a1, a2, a3, s]], [[s], [a0, s], [a1, s], [a0, a1, s], [a2, s], [a0, a2, s], [a1, a2, s], [a0, a1, a2, s], [a3, s], [a0, a3, s], [a1, a3, s], [a0, a1, a3, s], [a2, a3, s], [a0, a2, a3, s], [a1, a2, a3, s], [a0, a1, a2, a3, s]], Yes, Yes, Yes, No, equal_feasible_flow_and_cut_values_certify_both_optimal_without_integrality_or_algorithm_claims)

The full substitutions and premise checks give the original answer; source identity,format and status are unchanged.





## This question review and source binding

Review date: 2026-10-26

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: adf7148cd4b92afa4cbde6aba45a7bd57daf1d9a1777848ee59a09ebedc4562e
- candidate record SHA-256: dab6639ecbe57c8d00aa1d3f0eeba3941a3c10f8a0f005efc1b0c27b6056742a
- semantic review receipt SHA-256: 74c63a2c12285a3b2073f8d9f102bc2ba5fb7ed890c5b7c3b8afa94f032eda82
- question-first witness SHA-256: 6d56428610f8e86c45fd00a2ad3b27ad9c052956946f0b91d71a68536f79d95f
- Lean: NOT_RUN · human review: NOT_PERFORMED

[Same-source full JSON](https://ocme.evemisslab.com/data/question-derivations/questions/q-20261015-advance-20261115-r05-max-flow-min-cut-theorem-0098.json)