LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passaudited 2026-08-02

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Augmenting by the residual bottleneck preserves feasibility and increases the flow value

Statement

If $P$ is an $s$ - $t$ residual path for a feasible integral flow $f$ , and $δ$ is the least residual capacity of a copy on $P$ , then adding $δ$ on each original arc used as $(a, +)$ and subtracting $δ$ on each original arc used as $(a, -)$ gives a feasible integral flow $f^{'}$ with $∣ f^{'} ∣ = ∣ f ∣ + δ$ .

Facts & Assumptions

Given: A feasible integral flow $f$ , a labelled residual $s$ - $t$ path $P$ , and its bottleneck $δ$ .

[F1]

A forward copy $(a, +)$ has residual capacity $c (a) - f (a)$ , a reverse copy $(a, -)$ has residual capacity $f (a)$ , and the source has no entering original arc (Finite integral networks, feasible flows, values, cuts and residual networks).

Proof

technique · constructive

1.1

For every forward copy on $P$ , $δ \leq c (a) - f (a)$ , and for every reverse copy, $δ \leq f (a)$ ; the stated additions and subtractions therefore keep every new arc value in $[0, c (a)] \cap N$ .

F1construct

1.2

At each internal vertex of the residual path exactly one $δ$ -change enters and one leaves, so the altered flow still satisfies conservation there.

1.3

The first residual copy leaving $s$ is forward, since no original arc enters $s$ ; it raises the outgoing source flow by $δ$ , while all other source incidences are unchanged.

2.1

Steps 1.1--1.3 prove that $f^{'}$ is feasible and that $∣ f^{'} ∣ = ∣ f ∣ + δ$ .

step 1.1step 1.2step 1.3discharge-construct∎

Remarks

The sign is attached to an arc label, not merely to its endpoints. This is what keeps a reverse copy separate from an antiparallel original arc.

Depends on

Used by

Ford-Fulkerson terminates for finite integer capacities and proves max-flow min-cut with an integral maximum flow Theorem

Dependency tree · two levels

7 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

M. Goemans, Lecture notes on flows and cuts (standard reference, not scraped)