LemmaStatement: Literature-sourcedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck 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 $\delta$ is the least residual capacity of a copy on $P$ , then adding $\delta$ on each original arc used as $(a,+)$ and subtracting $\delta$ on each original arc used as $(a,-)$ gives a feasible integral flow $f'$ with $|f'|=|f|+\delta$ .

Facts & Assumptions

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

[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$ , $\delta\le c(a)-f(a)$ , and for every reverse copy, $\delta\le f(a)$ ; the stated additions and subtractions therefore keep every new arc value in $[0,c(a)]\cap\mathbb N$ .

F1construct

1.2

At each internal vertex of the residual path exactly one $\delta$ -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 $\delta$ , while all other source incidences are unchanged.

2.1

Steps 1.1--1.3 prove that $f'$ is feasible and that $|f'|=|f|+\delta$ .

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 · next 3 levels

Direct dependencies and their dependencies through the next three levels: 22 results over 13 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

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