Question 25952: A Feasible Flow Is Bounded above by Every Cut, Not Automatically Maximum

On this page

Original question and givens
Definition and scope
Step-by-step derivation
Reverse checks
Result
This question review and source binding

← Question derivation index · Original question batch

R0050-25952 · q-20261015-advance-20261115-r05-max-flow-min-cut-theorem-0027

Original question and givens

Use complete directed vertices=[s, a0, a1, a2, t], ordered edges=[[s, a0], [a0, t], [s, a1], [a1, t], [s, a2], [a2, t]], source=s, sink=t, aligned nonnegative exact capacities=[3, 3, 4, 4, 5, 5], candidate flows=[2, 2, 3, 3, 4, 4]. A cut contains the source and excludes the sink; its capacity sums only edges leaving the cut, not incoming edges. Give (source_value, sink_value, flow_cut_rows, all_cut_bounds_hold, automatic_maximum_claim, certificate).

G001 — Use complete directed vertices=[s, a0, a1, a2, t], ordered edges=[[s, a0], [a0, t], [s, a1], [a1, t], [s, a2], [a2, t]], source=s, sink=t, aligned nonnegative exact capacities=[3, 3, 4, 4, 5, 5], candidate flows=[2, 2, 3, 3, 4, 4]. A cut contains the source and excludes the sink; its capacity sums only edges leaving the cut, not incoming edges. Give (source_value, sink_value, flow_cut_rows, all_cut_bounds_hold, automatic_maximum_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

Step-by-step derivation

S001 · implies

Before

source roles = [mfmc-flow-cut-upper-bound]

After

derived = [[source_value, sink_value, flow_cut_rows, all_cut_bounds_hold, automatic_maximum_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 dependencies

Rule: source_ordered_fields_without_JS · Uses: G001

S002 · implies

Before

source roles = [[s, a0, a1, a2, t], [[s, a0], [a0, t], [s, a1], [a1, t], [s, a2], [a2, t]], [3, 3, 4, 4, 5, 5], [2, 2, 3, 3, 4, 4], s, t]

After

derived = [[a0, a1, a2, s, t], [[a0, t], [a1, t], [a2, t], [s, a0], [s, a1], [s, a2]], [3, 4, 5, 3, 4, 5], [2, 3, 4, 2, 3, 4]]

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 dependencies

Rule: MFMC_complete_directed_network_ZIP_before_source_order · Uses: G001, S001

S003 · calculation

Before

MFMC cut mask0 OUTWARD capacity := sum(3, 4, 5)

After

MFMC cut mask0 OUTWARD capacity = 12

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S002

S004 · implies

Before

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

After

derived = [[3, 4, 5], [], [[[s, a0], 3], [[s, a1], 4], [[s, a2], 5]], 12]

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 dependencies

Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S003

S005 · calculation

Before

MFMC cut mask1 OUTWARD capacity := sum(3, 4, 5)

After

MFMC cut mask1 OUTWARD capacity = 12

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S004

S006 · implies

Before

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

After

derived = [[0, 4, 5], [], [[[a0, t], 3], [[s, a1], 4], [[s, a2], 5]], 12]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S005

S007 · calculation

Before

MFMC cut mask2 OUTWARD capacity := sum(4, 3, 5)

After

MFMC cut mask2 OUTWARD capacity = 12

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S006

S008 · implies

Before

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

After

derived = [[1, 3, 5], [], [[[a1, t], 4], [[s, a0], 3], [[s, a2], 5]], 12]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S007

S009 · calculation

Before

MFMC cut mask3 OUTWARD capacity := sum(3, 4, 5)

After

MFMC cut mask3 OUTWARD capacity = 12

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S008

S010 · implies

Before

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

After

derived = [[0, 1, 5], [], [[[a0, t], 3], [[a1, t], 4], [[s, a2], 5]], 12]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S009

S011 · calculation

Before

MFMC cut mask4 OUTWARD capacity := sum(5, 3, 4)

After

MFMC cut mask4 OUTWARD capacity = 12

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S010

S012 · implies

Before

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

After

derived = [[2, 3, 4], [], [[[a2, t], 5], [[s, a0], 3], [[s, a1], 4]], 12]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S011

S013 · calculation

Before

MFMC cut mask5 OUTWARD capacity := sum(3, 5, 4)

After

MFMC cut mask5 OUTWARD capacity = 12

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S012

S014 · implies

Before

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

After

derived = [[0, 2, 4], [], [[[a0, t], 3], [[a2, t], 5], [[s, a1], 4]], 12]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S013

S015 · calculation

Before

MFMC cut mask6 OUTWARD capacity := sum(4, 5, 3)

After

MFMC cut mask6 OUTWARD capacity = 12

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S014

S016 · implies

Before

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

After

derived = [[1, 2, 3], [], [[[a1, t], 4], [[a2, t], 5], [[s, a0], 3]], 12]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S015

S017 · calculation

Before

MFMC cut mask7 OUTWARD capacity := sum(3, 4, 5)

After

MFMC cut mask7 OUTWARD capacity = 12

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S016

S018 · implies

Before

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

After

derived = [[0, 1, 2], [], [[[a0, t], 3], [[a1, t], 4], [[a2, t], 5]], 12]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S017

S019 · implies

Before

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

After

derived = [8, 8, 12, [[s], [a0, s], [a1, s], [a0, a1, s], [a2, s], [a0, a2, s], [a1, a2, s], [a0, a1, a2, 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 dependencies

Rule: MFMC_ALL_cut_family_complete_minimum_and_ALL_ties · Uses: G001, S018

S020 · calculation

Before

MFMC vertex a0 ALL incoming := sum(2)

After

MFMC vertex a0 ALL incoming = 2

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S019

S021 · calculation

Before

MFMC vertex a0 ALL outgoing := sum(2)

After

MFMC vertex a0 ALL outgoing = 2

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S020

S022 · calculation

Before

MFMC vertex a1 ALL incoming := sum(3)

After

MFMC vertex a1 ALL incoming = 3

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S021

S023 · calculation

Before

MFMC vertex a1 ALL outgoing := sum(3)

After

MFMC vertex a1 ALL outgoing = 3

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S022

S024 · calculation

Before

MFMC vertex a2 ALL incoming := sum(4)

After

MFMC vertex a2 ALL incoming = 4

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S023

S025 · calculation

Before

MFMC vertex a2 ALL outgoing := sum(4)

After

MFMC vertex a2 ALL outgoing = 4

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S024

S026 · calculation

Before

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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S025

S027 · calculation

Before

MFMC vertex s ALL outgoing := sum(2, 3, 4)

After

MFMC vertex s ALL outgoing = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S026

S028 · calculation

Before

MFMC vertex t ALL incoming := sum(2, 3, 4)

After

MFMC vertex t ALL incoming = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S027

S029 · calculation

Before

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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S028

S030 · calculation

Before

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

After

MFMC SOURCE net out not gross = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S029

S031 · calculation

Before

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

After

MFMC SINK net in not gross = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S030

S032 · implies

Before

source roles = [[[a0, t], [a1, t], [a2, t], [s, a0], [s, a1], [s, a2]], [2, 3, 4, 2, 3, 4], [3, 4, 5, 3, 4, 5], s, t]

After

derived = [[[[a0, t], 2, 3, Yes], [[a1, t], 3, 4, Yes], [[a2, t], 4, 5, Yes], [[s, a0], 2, 3, Yes], [[s, a1], 3, 4, Yes], [[s, a2], 4, 5, Yes]], [[a0, 2, 2, Yes], [a1, 3, 3, Yes], [a2, 4, 4, Yes]], Yes, Yes, 9, 9, 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 dependencies

Rule: MFMC_EVERY_capacity_EVERY_internal_balance_source_sink_NET_feasibility · Uses: G001, S031

S033 · calculation

Before

MFMC cut mask0 OUTWARD flow := sum(2, 3, 4)

After

MFMC cut mask0 OUTWARD flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S032

S034 · calculation

Before

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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S033

S035 · calculation

Before

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

After

MFMC cut mask0 NET flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S034

S036 · implies

Before

source roles = [[s], [3, 4, 5], [], 9]

After

derived = [[[s], 9, 0, 9, 12, 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 dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S035

S037 · calculation

Before

MFMC cut mask1 OUTWARD flow := sum(2, 3, 4)

After

MFMC cut mask1 OUTWARD flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S036

S038 · calculation

Before

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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S037

S039 · calculation

Before

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

After

MFMC cut mask1 NET flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S038

S040 · implies

Before

source roles = [[a0, s], [0, 4, 5], [], 9]

After

derived = [[[a0, s], 9, 0, 9, 12, Yes, Yes]]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S039

S041 · calculation

Before

MFMC cut mask2 OUTWARD flow := sum(3, 2, 4)

After

MFMC cut mask2 OUTWARD flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S040

S042 · calculation

Before

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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S041

S043 · calculation

Before

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

After

MFMC cut mask2 NET flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S042

S044 · implies

Before

source roles = [[a1, s], [1, 3, 5], [], 9]

After

derived = [[[a1, s], 9, 0, 9, 12, Yes, Yes]]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S043

S045 · calculation

Before

MFMC cut mask3 OUTWARD flow := sum(2, 3, 4)

After

MFMC cut mask3 OUTWARD flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S044

S046 · calculation

Before

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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S045

S047 · calculation

Before

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

After

MFMC cut mask3 NET flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S046

S048 · implies

Before

source roles = [[a0, a1, s], [0, 1, 5], [], 9]

After

derived = [[[a0, a1, s], 9, 0, 9, 12, Yes, Yes]]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S047

S049 · calculation

Before

MFMC cut mask4 OUTWARD flow := sum(4, 2, 3)

After

MFMC cut mask4 OUTWARD flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S048

S050 · calculation

Before

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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S049

S051 · calculation

Before

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

After

MFMC cut mask4 NET flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S050

S052 · implies

Before

source roles = [[a2, s], [2, 3, 4], [], 9]

After

derived = [[[a2, s], 9, 0, 9, 12, Yes, Yes]]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S051

S053 · calculation

Before

MFMC cut mask5 OUTWARD flow := sum(2, 4, 3)

After

MFMC cut mask5 OUTWARD flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S052

S054 · calculation

Before

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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S053

S055 · calculation

Before

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

After

MFMC cut mask5 NET flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S054

S056 · implies

Before

source roles = [[a0, a2, s], [0, 2, 4], [], 9]

After

derived = [[[a0, a2, s], 9, 0, 9, 12, Yes, Yes]]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S055

S057 · calculation

Before

MFMC cut mask6 OUTWARD flow := sum(3, 4, 2)

After

MFMC cut mask6 OUTWARD flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S056

S058 · calculation

Before

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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S057

S059 · calculation

Before

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

After

MFMC cut mask6 NET flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S058

S060 · implies

Before

source roles = [[a1, a2, s], [1, 2, 3], [], 9]

After

derived = [[[a1, a2, s], 9, 0, 9, 12, Yes, Yes]]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S059

S061 · calculation

Before

MFMC cut mask7 OUTWARD flow := sum(2, 3, 4)

After

MFMC cut mask7 OUTWARD flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S060

S062 · calculation

Before

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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S061

S063 · calculation

Before

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

After

MFMC cut mask7 NET flow = 9

Conditions: none

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

Step identifiers and dependencies

Rule: exact_rational_arithmetic · Uses: G001, S062

S064 · implies

Before

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

After

derived = [[[a0, a1, a2, s], 9, 0, 9, 12, Yes, Yes]]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S063

Reverse checks

S064 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
S063 · premise_and_result_audit — Recompute MFMC cut mask7 NET flow with exact rational arithmetic, not rounded decimals.
S062 · premise_and_result_audit — Recompute MFMC cut mask7 INWARD flow with exact rational arithmetic, not rounded decimals.
S061 · premise_and_result_audit — Recompute MFMC cut mask7 OUTWARD flow with exact rational arithmetic, not rounded decimals.
S060 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
S059 · premise_and_result_audit — Recompute MFMC cut mask6 NET flow with exact rational arithmetic, not rounded decimals.
S058 · premise_and_result_audit — Recompute MFMC cut mask6 INWARD flow with exact rational arithmetic, not rounded decimals.
S057 · premise_and_result_audit — Recompute MFMC cut mask6 OUTWARD flow with exact rational arithmetic, not rounded decimals.
S056 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
S055 · premise_and_result_audit — Recompute MFMC cut mask5 NET flow with exact rational arithmetic, not rounded decimals.
S054 · premise_and_result_audit — Recompute MFMC cut mask5 INWARD flow with exact rational arithmetic, not rounded decimals.
S053 · premise_and_result_audit — Recompute MFMC cut mask5 OUTWARD flow with exact rational arithmetic, not rounded decimals.
S052 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
S051 · premise_and_result_audit — Recompute MFMC cut mask4 NET flow with exact rational arithmetic, not rounded decimals.
S050 · premise_and_result_audit — Recompute MFMC cut mask4 INWARD flow with exact rational arithmetic, not rounded decimals.
S049 · premise_and_result_audit — Recompute MFMC cut mask4 OUTWARD flow with exact rational arithmetic, not rounded decimals.
S048 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
S047 · premise_and_result_audit — Recompute MFMC cut mask3 NET flow with exact rational arithmetic, not rounded decimals.
S046 · premise_and_result_audit — Recompute MFMC cut mask3 INWARD flow with exact rational arithmetic, not rounded decimals.
S045 · premise_and_result_audit — Recompute MFMC cut mask3 OUTWARD flow with exact rational arithmetic, not rounded decimals.
S044 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
S043 · premise_and_result_audit — Recompute MFMC cut mask2 NET flow with exact rational arithmetic, not rounded decimals.
S042 · premise_and_result_audit — Recompute MFMC cut mask2 INWARD flow with exact rational arithmetic, not rounded decimals.
S041 · premise_and_result_audit — Recompute MFMC cut mask2 OUTWARD flow with exact rational arithmetic, not rounded decimals.
S040 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
S039 · premise_and_result_audit — Recompute MFMC cut mask1 NET flow with exact rational arithmetic, not rounded decimals.
S038 · premise_and_result_audit — Recompute MFMC cut mask1 INWARD flow with exact rational arithmetic, not rounded decimals.
S037 · premise_and_result_audit — Recompute MFMC cut mask1 OUTWARD flow with exact rational arithmetic, not rounded decimals.
S036 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
S035 · premise_and_result_audit — Recompute MFMC cut mask0 NET flow with exact rational arithmetic, not rounded decimals.
S034 · premise_and_result_audit — Recompute MFMC cut mask0 INWARD flow with exact rational arithmetic, not rounded decimals.
S033 · premise_and_result_audit — Recompute MFMC cut mask0 OUTWARD flow 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 SINK net in not gross with exact rational arithmetic, not rounded decimals.
S030 · premise_and_result_audit — Recompute MFMC SOURCE net out not gross with exact rational arithmetic, not rounded decimals.
S029 · premise_and_result_audit — Recompute MFMC vertex t ALL outgoing with exact rational arithmetic, not rounded decimals.
S028 · premise_and_result_audit — Recompute MFMC vertex t ALL incoming with exact rational arithmetic, not rounded decimals.
S027 · premise_and_result_audit — Recompute MFMC vertex s ALL outgoing with exact rational arithmetic, not rounded decimals.
S026 · premise_and_result_audit — Recompute MFMC vertex s ALL incoming with exact rational arithmetic, not rounded decimals.
S025 · premise_and_result_audit — Recompute MFMC vertex a2 ALL outgoing with exact rational arithmetic, not rounded decimals.
S024 · premise_and_result_audit — Recompute MFMC vertex a2 ALL incoming with exact rational arithmetic, not rounded decimals.
S023 · premise_and_result_audit — Recompute MFMC vertex a1 ALL outgoing with exact rational arithmetic, not rounded decimals.
S022 · premise_and_result_audit — Recompute MFMC vertex a1 ALL incoming with exact rational arithmetic, not rounded decimals.
S021 · premise_and_result_audit — Recompute MFMC vertex a0 ALL outgoing with exact rational arithmetic, not rounded decimals.
S020 · premise_and_result_audit — Recompute MFMC vertex a0 ALL incoming with exact rational arithmetic, not rounded decimals.
S019 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
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

(9, 9, [[[s], 9, 0, 9, 12, Yes, Yes], [[a0, s], 9, 0, 9, 12, Yes, Yes], [[a1, s], 9, 0, 9, 12, Yes, Yes], [[a0, a1, s], 9, 0, 9, 12, Yes, Yes], [[a2, s], 9, 0, 9, 12, Yes, Yes], [[a0, a2, s], 9, 0, 9, 12, Yes, Yes], [[a1, a2, s], 9, 0, 9, 12, Yes, Yes], [[a0, a1, a2, s], 9, 0, 9, 12, Yes, Yes]], Yes, No, every_feasible_flow_value_is_at_most_every_cut_capacity_but_need_not_be_maximum)

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

Same-source full JSON