Question 25963: 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-25963 · q-20261015-advance-20261115-r05-max-flow-min-cut-theorem-0038

Original question and givens

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

After

derived = [[a0, a1, s, t], [[a0, s], [a0, t], [a1, t], [s, a0], [s, a1]], [19, 14, 15, 14, 15], [0, 13, 14, 13, 14]]

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(14, 15)

After

MFMC cut mask0 OUTWARD capacity = 29

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], [s]]

After

derived = [[3, 4], [0], [[[s, a0], 14], [[s, a1], 15]], 29]

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(14, 15)

After

MFMC cut mask1 OUTWARD capacity = 29

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], [a0, s]]

After

derived = [[1, 4], [], [[[a0, t], 14], [[s, a1], 15]], 29]

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(15, 14)

After

MFMC cut mask2 OUTWARD capacity = 29

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], [a1, s]]

After

derived = [[2, 3], [0], [[[a1, t], 15], [[s, a0], 14]], 29]

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(14, 15)

After

MFMC cut mask3 OUTWARD capacity = 29

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], [a0, a1, s]]

After

derived = [[1, 2], [], [[[a0, t], 14], [[a1, t], 15]], 29]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_numeric_mask_cut_OUTWARD_edges_only · Uses: G001, S009

S011 · implies

Before

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

After

derived = [4, 4, 29, [[s], [a0, s], [a1, s], [a0, a1, 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, S010

S012 · calculation

Before

MFMC vertex a0 ALL incoming := sum(13)

After

MFMC vertex a0 ALL incoming = 13

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, S011

S013 · calculation

Before

MFMC vertex a0 ALL outgoing := sum(0, 13)

After

MFMC vertex a0 ALL outgoing = 13

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 · calculation

Before

MFMC vertex a1 ALL incoming := sum(14)

After

MFMC vertex a1 ALL incoming = 14

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, S013

S015 · calculation

Before

MFMC vertex a1 ALL outgoing := sum(14)

After

MFMC vertex a1 ALL outgoing = 14

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 · calculation

Before

MFMC vertex s ALL incoming := sum(0)

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, S015

S017 · calculation

Before

MFMC vertex s ALL outgoing := sum(13, 14)

After

MFMC vertex s 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S016

S018 · calculation

Before

MFMC vertex t ALL incoming := sum(13, 14)

After

MFMC vertex t 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S017

S019 · 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, S018

S020 · calculation

Before

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

After

MFMC SOURCE net out not gross = 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S019

S021 · calculation

Before

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

After

MFMC SINK net in not gross = 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S020

S022 · implies

Before

source roles = [[[a0, s], [a0, t], [a1, t], [s, a0], [s, a1]], [0, 13, 14, 13, 14], [19, 14, 15, 14, 15], s, t]

After

derived = [[[[a0, s], 0, 19, Yes], [[a0, t], 13, 14, Yes], [[a1, t], 14, 15, Yes], [[s, a0], 13, 14, Yes], [[s, a1], 14, 15, Yes]], [[a0, 13, 13, Yes], [a1, 14, 14, Yes]], Yes, Yes, 27, 27, 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, S021

S023 · calculation

Before

MFMC cut mask0 OUTWARD flow := sum(13, 14)

After

MFMC cut mask0 OUTWARD flow = 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S022

S024 · calculation

Before

MFMC cut mask0 INWARD flow := sum(0)

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, S023

S025 · calculation

Before

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

After

MFMC cut mask0 NET flow = 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S024

S026 · implies

Before

source roles = [[s], [3, 4], [0], 27]

After

derived = [[[s], 27, 0, 27, 29, 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, S025

S027 · calculation

Before

MFMC cut mask1 OUTWARD flow := sum(13, 14)

After

MFMC cut mask1 OUTWARD flow = 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S026

S028 · 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, S027

S029 · calculation

Before

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

After

MFMC cut mask1 NET flow = 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S028

S030 · implies

Before

source roles = [[a0, s], [1, 4], [], 27]

After

derived = [[[a0, s], 27, 0, 27, 29, Yes, Yes]]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S029

S031 · calculation

Before

MFMC cut mask2 OUTWARD flow := sum(14, 13)

After

MFMC cut mask2 OUTWARD flow = 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S030

S032 · calculation

Before

MFMC cut mask2 INWARD flow := sum(0)

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, S031

S033 · calculation

Before

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

After

MFMC cut mask2 NET flow = 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S032

S034 · implies

Before

source roles = [[a1, s], [2, 3], [0], 27]

After

derived = [[[a1, s], 27, 0, 27, 29, Yes, Yes]]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S033

S035 · calculation

Before

MFMC cut mask3 OUTWARD flow := sum(13, 14)

After

MFMC cut mask3 OUTWARD flow = 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S034

S036 · 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, S035

S037 · calculation

Before

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

After

MFMC cut mask3 NET flow = 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 dependencies

Rule: exact_rational_arithmetic · Uses: G001, S036

S038 · implies

Before

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

After

derived = [[[a0, a1, s], 27, 0, 27, 29, Yes, Yes]]

Conditions: none

Step identifiers and dependencies

Rule: MFMC_EVERY_cut_conservation_cancellation_and_weak_upper_bound · Uses: G001, S037

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

(27, 27, [[[s], 27, 0, 27, 29, Yes, Yes], [[a0, s], 27, 0, 27, 29, Yes, Yes], [[a1, s], 27, 0, 27, 29, Yes, Yes], [[a0, a1, s], 27, 0, 27, 29, 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: 43527d34394e847dbbe1520ab64e0caac876fe5c2a2e8f316263b03348164a69
candidate record SHA-256: f85cf5da34fbfc128aeb10451c6764fdde59415bb12899fd7cb1b1c2233bbb5d
semantic review receipt SHA-256: 74c63a2c12285a3b2073f8d9f102bc2ba5fb7ed890c5b7c3b8afa94f032eda82
question-first witness SHA-256: 6d56428610f8e86c45fd00a2ad3b27ad9c052956946f0b91d71a68536f79d95f
Lean: NOT_RUN · human review: NOT_PERFORMED

Same-source full JSON