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

Original question and givens

Use complete directed vertices=[s, a0, a1, t], ordered edges=[[s, a0], [a0, t], [s, a1], [a1, t]], source=s, sink=t, aligned nonnegative exact capacities=[18, 18, 19, 19], candidate flows=[17, 17, 18, 18]. 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, t], ordered edges=[[s, a0], [a0, t], [s, a1], [a1, t]], source=s, sink=t, aligned nonnegative exact capacities=[18, 18, 19, 19], candidate flows=[17, 17, 18, 18]. 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

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

derived = [[source_value, sink_value, flow_cut_rows, all_cut_bounds_hold, automatic_maximum_claim, certificate]]

source roles = [[s, a0, a1, t], [[s, a0], [a0, t], [s, a1], [a1, t]], [18, 18, 19, 19], [17, 17, 18, 18], s, t]

derived = [[a0, a1, s, t], [[a0, t], [a1, t], [s, a0], [s, a1]], [18, 19, 18, 19], [17, 18, 17, 18]]

MFMC cut mask0 OUTWARD capacity := sum(18, 19)

MFMC cut mask0 OUTWARD capacity = 37

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

derived = [[2, 3], [], [[[s, a0], 18], [[s, a1], 19]], 37]

MFMC cut mask1 OUTWARD capacity := sum(18, 19)

MFMC cut mask1 OUTWARD capacity = 37

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

derived = [[0, 3], [], [[[a0, t], 18], [[s, a1], 19]], 37]

MFMC cut mask2 OUTWARD capacity := sum(19, 18)

MFMC cut mask2 OUTWARD capacity = 37

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

derived = [[1, 2], [], [[[a1, t], 19], [[s, a0], 18]], 37]

MFMC cut mask3 OUTWARD capacity := sum(18, 19)

MFMC cut mask3 OUTWARD capacity = 37

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

derived = [[0, 1], [], [[[a0, t], 18], [[a1, t], 19]], 37]

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

derived = [4, 4, 37, [[s], [a0, s], [a1, s], [a0, a1, s]]]

MFMC vertex a0 ALL incoming := sum(17)

MFMC vertex a0 ALL incoming = 17

MFMC vertex a0 ALL outgoing := sum(17)

MFMC vertex a0 ALL outgoing = 17

MFMC vertex a1 ALL incoming := sum(18)

MFMC vertex a1 ALL incoming = 18

MFMC vertex a1 ALL outgoing := sum(18)

MFMC vertex a1 ALL outgoing = 18

MFMC vertex s ALL incoming := sum()

MFMC vertex s ALL incoming = 0

MFMC vertex s ALL outgoing := sum(17, 18)

MFMC vertex s ALL outgoing = 35

MFMC vertex t ALL incoming := sum(17, 18)

MFMC vertex t ALL incoming = 35

MFMC vertex t ALL outgoing := sum()

MFMC vertex t ALL outgoing = 0

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

MFMC SOURCE net out not gross = 35

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

MFMC SINK net in not gross = 35

source roles = [[[a0, t], [a1, t], [s, a0], [s, a1]], [17, 18, 17, 18], [18, 19, 18, 19], s, t]

derived = [[[[a0, t], 17, 18, Yes], [[a1, t], 18, 19, Yes], [[s, a0], 17, 18, Yes], [[s, a1], 18, 19, Yes]], [[a0, 17, 17, Yes], [a1, 18, 18, Yes]], Yes, Yes, 35, 35, Yes, Yes]

MFMC cut mask0 OUTWARD flow := sum(17, 18)

MFMC cut mask0 OUTWARD flow = 35

MFMC cut mask0 INWARD flow := sum()

MFMC cut mask0 INWARD flow = 0

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

MFMC cut mask0 NET flow = 35

source roles = [[s], [2, 3], [], 35]

derived = [[[s], 35, 0, 35, 37, Yes, Yes]]

MFMC cut mask1 OUTWARD flow := sum(17, 18)

MFMC cut mask1 OUTWARD flow = 35

MFMC cut mask1 INWARD flow := sum()

MFMC cut mask1 INWARD flow = 0

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

MFMC cut mask1 NET flow = 35

source roles = [[a0, s], [0, 3], [], 35]

derived = [[[a0, s], 35, 0, 35, 37, Yes, Yes]]

MFMC cut mask2 OUTWARD flow := sum(18, 17)

MFMC cut mask2 OUTWARD flow = 35

MFMC cut mask2 INWARD flow := sum()

MFMC cut mask2 INWARD flow = 0

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

MFMC cut mask2 NET flow = 35

source roles = [[a1, s], [1, 2], [], 35]

derived = [[[a1, s], 35, 0, 35, 37, Yes, Yes]]

MFMC cut mask3 OUTWARD flow := sum(17, 18)

MFMC cut mask3 OUTWARD flow = 35

MFMC cut mask3 INWARD flow := sum()

MFMC cut mask3 INWARD flow = 0

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

MFMC cut mask3 NET flow = 35

source roles = [[a0, a1, s], [0, 1], [], 35]

derived = [[[a0, a1, s], 35, 0, 35, 37, Yes, Yes]]

Reverse checks

• S038 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• S037 · premise_and_result_audit — Recompute MFMC cut mask3 NET flow with exact rational arithmetic, not rounded decimals.
• S036 · premise_and_result_audit — Recompute MFMC cut mask3 INWARD flow with exact rational arithmetic, not rounded decimals.
• S035 · premise_and_result_audit — Recompute MFMC cut mask3 OUTWARD flow with exact rational arithmetic, not rounded decimals.
• 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 mask2 NET flow with exact rational arithmetic, not rounded decimals.
• S032 · premise_and_result_audit — Recompute MFMC cut mask2 INWARD flow with exact rational arithmetic, not rounded decimals.
• S031 · premise_and_result_audit — Recompute MFMC cut mask2 OUTWARD flow 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 mask1 NET flow with exact rational arithmetic, not rounded decimals.
• S028 · premise_and_result_audit — Recompute MFMC cut mask1 INWARD flow with exact rational arithmetic, not rounded decimals.
• S027 · premise_and_result_audit — Recompute MFMC cut mask1 OUTWARD flow 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 mask0 NET flow with exact rational arithmetic, not rounded decimals.
• S024 · premise_and_result_audit — Recompute MFMC cut mask0 INWARD flow with exact rational arithmetic, not rounded decimals.
• S023 · premise_and_result_audit — Recompute MFMC cut mask0 OUTWARD flow 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 SINK net in not gross with exact rational arithmetic, not rounded decimals.
• S020 · premise_and_result_audit — Recompute MFMC SOURCE net out not gross with exact rational arithmetic, not rounded decimals.
• S019 · premise_and_result_audit — Recompute MFMC vertex t ALL outgoing with exact rational arithmetic, not rounded decimals.
• S018 · premise_and_result_audit — Recompute MFMC vertex t ALL incoming with exact rational arithmetic, not rounded decimals.
• S017 · premise_and_result_audit — Recompute MFMC vertex s ALL outgoing with exact rational arithmetic, not rounded decimals.
• S016 · premise_and_result_audit — Recompute MFMC vertex s ALL incoming with exact rational arithmetic, not rounded decimals.
• S015 · premise_and_result_audit — Recompute MFMC vertex a1 ALL outgoing with exact rational arithmetic, not rounded decimals.
• S014 · premise_and_result_audit — Recompute MFMC vertex a1 ALL incoming with exact rational arithmetic, not rounded decimals.
• S013 · premise_and_result_audit — Recompute MFMC vertex a0 ALL outgoing with exact rational arithmetic, not rounded decimals.
• S012 · premise_and_result_audit — Recompute MFMC vertex a0 ALL incoming with exact rational arithmetic, not rounded decimals.
• S011 · premise_and_result_audit — Check against the original data and this step's premises; a one-way implication is not an equivalence.
• 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

(35, 35, [[[s], 35, 0, 35, 37, Yes, Yes], [[a0, s], 35, 0, 35, 37, Yes, Yes], [[a1, s], 35, 0, 35, 37, Yes, Yes], [[a0, a1, s], 35, 0, 35, 37, 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.