Math 2.0

Combinatorics Theorem

Flow value is at most cut capacity

Builds on Directed graphFlow network

Statement

Let GG be a flow network on a finite directed graph. It has a source ss, a sink tt, and a capacity c(e)≥0c(e) \ge 0 on each edge ee.

Let ϕ\phi be a flow in GG. That is, 0≤ϕ(e)≤c(e)0 \le \phi(e) \le c(e) for each edge ee, and at each vertex other than ss and tt the flow in equals the flow out.

Let V=L∪UV = L \cup U be a cut. That is, LL and UU are disjoint, s∈Ls \in L and t∈Ut \in U. The capacity of the cut is the sum of c(e)c(e) over the edges that go from LL to UU.

Then the value of ϕ\phi is at most the capacity of the cut.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Directed graph definition
  2. Flow network concept
  3. Flow value is at most cut capacity statement

Further reading

  1. Web https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_networkflow_flows-cuts.ptx#L36, source/s_networkflow_flows-cuts.ptx:36
About this page
Tag7TQK5EC8B8
URIm2://7TQK5EC8B8
Kindstatement, theorem
WritingW1 stated
MSC05C21, 90B10, 90C35
StatusThis copy of the site has no build data. Run m2 status 7TQK5EC8B8.
UsesDirected graph, Flow network
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge about out: the concepts that the statement is about (0 of 1)
  • edge proves in: at least one proof node (0 of 1)
  • edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
  • explanation L2 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.