Let \(N\) be a network on a finite vertex set \(V\), let \(f\) assign a nonnegative integer \(f(u,v)\) to each ordered pair of vertices \(u,v\), and let \(S\subseteq V\). Summing the resultant flow out of a singleton \(\{ v\} \) over all vertices \(v\in S\) recovers the resultant flow out of \(S\); that is, the following identity holds in \(\mathbb {Z}\):

Let \(N\) be a network with disjoint nonempty source set \(X\) and sink set \(Y\), and let \(f\) be a flow in \(N\). For a vertex set \(S\), write \(f^{+}(S)\) for the total flow along the arcs directed from \(S\) to its complement and \(f^{-}(S)\) for the total flow along the arcs directed from the complement into \(S\). Then

Let \(N\) be a network with source set \(X\), a single distinguished source vertex \(x\), and a single distinguished sink vertex \(y\); let \(f\) be a flow in \(N\); and let \(S\) be a set of vertices forming a cut, so that \(x \in S\) and \(y \notin S\). Then the value \(\operatorname {val} f = f^{+}(X) - f^{-}(X)\) of the flow is equal to the resultant flow out of \(S\):

Let \(N\) be a network with disjoint nonempty source set \(X\) and sink set \(Y\), distinguished source \(x\) and sink \(y\), and integer capacity function \(c\). Let \(f\) be a flow in \(N\), and let \((S,\bar S)\) be a cut, so that \(x\in S\) and \(y\notin S\). Then the value of \(f\) is at most the capacity of the cut:

Let \(N\) be a network with capacity function \(c\), distinguished source \(x\) and sink \(y\), let \(f\) be a flow in \(N\), and let \(S\) be a vertex set defining a cut, so that \(x \in S\) and \(y \notin S\); write \(\bar S\) for the complementary vertex set. Then the value of the flow equals the capacity of the cut, \(\mathrm{val}(f) = \mathrm{cap}(S,\bar S)\), if and only if \(f(u,v) = c(u,v)\) for every arc with \(u \in S\) and \(v \in \bar S\) (each forward arc across the cut is saturated) and \(f(u,v) = 0\) for every arc with \(u \in \bar S\) and \(v \in S\) (each backward arc across the cut carries no flow).

Let \(N\) be a network with single source \(x\) and single sink \(y\), let \(f\) be a flow in \(N\), and let \((S, \bar S)\) be a cut of \(N\), so that \(x \in S\) and \(y \notin S\). If the value of the flow equals the capacity of the cut, \(\mathrm{val}(f) = \mathrm{cap}(S)\), then \(f\) is a maximum flow in \(N\) and \((S,\bar S)\) is a minimum cut in \(N\).

Every network \(N\) on a finite vertex set admits a maximum flow: there exists a flow \(f\) in \(N\) such that \(\mathrm{val}(f') \le \mathrm{val}(f)\) for every flow \(f'\) in \(N\).

Let \(N\) be a network with distinguished single source \(x\) and single sink \(y\). Then \(N\) possesses a minimum cut: there exists a set \(S\) of vertices with \(x \in S\) and \(y \notin S\) whose capacity \(\sum _{u \in S}\sum _{v \notin S} c(u,v)\) is least among all sets separating \(x\) from \(y\) in this way.

Let \(N\) be a network with distinguished single source \(x\) and single sink \(y\), and suppose there is no directed path from \(x\) to \(y\) every arc of which has positive capacity. Then every maximum flow \(f\) in \(N\) has value \(0\), and every minimum cut \(S\) (a vertex set with \(x \in S\) and \(y \notin S\)) has capacity \(0\).

Let \(N\) be a network with a single source \(x\) and a single sink \(y\), and recall that a cut is determined by a vertex set \(S\) with \(x \in S\) and \(y \notin S\), its capacity being \(\sum _{u \in S}\sum _{v \notin S} c(u,v)\); a cut is a minimum cut if no cut has strictly smaller capacity. If the cuts determined by vertex sets \(S\) and \(T\) are both minimum cuts of \(N\), then the cuts determined by \(S \cup T\) and by \(S \cap T\) are also minimum cuts of \(N\).

Let \(N\) be a network — a finite digraph carrying a nonnegative integer capacity on each arc, with disjoint nonempty source and sink sets and a distinguished source \(x\) and sink \(y\) — and let \(f\) be a flow in \(N\). Then \(f\) is a maximum flow if and only if there is no \(f\)-incrementing path in \(N\) ending at the sink \(y\).

Let \(N\) be a network with a single source \(x\) and a single sink \(y\), and let \(f\) be a flow in \(N\). Suppose \(N\) contains no \(f\)-incrementing path from \(x\) to \(y\) — that is, no path from the source to the sink each of whose arcs is either a forward arc that is not yet saturated (\(f \lt c\)) or a backward arc carrying positive flow (\(f \gt 0\)). Then there is a cut \((S,\bar S)\), a set of vertices with \(x \in S\) and \(y \notin S\), whose capacity equals the value of \(f\):

Let \(N\) be a network on a finite vertex set, with capacity function \(c\), disjoint nonempty source and sink sets \(X\) and \(Y\), and a distinguished source \(x\) and sink \(y\) (Ford and Fulkerson, 1956). Then \(N\) admits a maximum flow \(f\) together with a minimum cut \((S,\bar S)\) — that is, \(x \in S\) and \(y \notin S\) — whose value and capacity coincide:

In particular, the value of a maximum flow in \(N\) equals the capacity of a minimum cut.

Let \(N\) be a network with distinguished source \(x\) and sink \(y\) whose capacity function takes only the values \(0\) and \(1\) (that is, every capacity is at most \(1\)), and let \(f\) be a maximum flow in \(N\). Then the value of \(f\) equals the maximum number of arc-disjoint directed \((x,y)\)-paths in \(N\).

Let \(N\) be a network with capacity function \(c\), a single source \(x\), and a single sink \(y\), and suppose every arc has capacity at most \(1\), that is \(c(u,v) \le 1\) for all vertices \(u,v\). For a set \(S\) of vertices with \(x \in S\) and \(y \notin S\), write \(\mathrm{cap}(S) = \sum _{u \in S}\sum _{v \notin S} c(u,v)\) for its cut capacity, and suppose \(S\) is a minimum cut, meaning \(\mathrm{cap}(S) \le \mathrm{cap}(S')\) for every set \(S'\) with \(x \in S'\) and \(y \notin S'\). Then \(\mathrm{cap}(S)\) equals the minimum number of arcs whose deletion destroys every directed \((x,y)\)-path in \(N\).

Let \(D\) be a finite digraph, and let \(x\) and \(y\) be two of its vertices. Then the maximum number of pairwise arc-disjoint directed paths from \(x\) to \(y\) equals the minimum number of arcs whose deletion destroys every directed path from \(x\) to \(y\).

Let \(G\) be a finite simple graph and let \(x\) and \(y\) be two of its vertices. Then the maximum number of pairwise edge-disjoint \((x,y)\)-paths in \(G\) equals the minimum number of edges whose deletion destroys every \((x,y)\)-path in \(G\).

Let \(G\) be a finite simple graph and let \(k\) be a natural number. Then the edge connectivity satisfies \(k \le \kappa '(G)\) if and only if, for every pair of distinct vertices \(u\) and \(v\), the maximum number of pairwise edge-disjoint paths joining \(u\) and \(v\) is at least \(k\).

Let \(D\) be a finite digraph and let \(x\) and \(y\) be two vertices of \(D\) with no arc from \(x\) to \(y\). Then the maximum number of pairwise internally-disjoint directed paths from \(x\) to \(y\) equals the minimum number of vertices (other than \(x\) and \(y\)) whose deletion destroys every directed path from \(x\) to \(y\).

Let \(G\) be a finite simple graph, and let \(x\) and \(y\) be two distinct, nonadjacent vertices of \(G\). Then the maximum number of internally disjoint \((x,y)\)-paths in \(G\) equals the minimum size of a set of vertices (necessarily distinct from \(x\) and \(y\)) whose deletion destroys every \((x,y)\)-path.

Let \(G\) be a simple graph on a finite vertex set \(V\), and let \(k\) be a natural number with \(|V| \ge k+1\). Then \(\kappa (G) \ge k\) if and only if every pair of distinct vertices \(u, v\) of \(G\) is joined by at least \(k\) internally disjoint \(u\)–\(v\) paths.

Let \(G\) be a finite simple graph, and let \(k \ge 2\) be an integer such that \(G\) is \(k\)-connected, that is, \(k \le \kappa (G)\). Then for any set \(T\) of exactly \(k\) vertices of \(G\), there is a cycle in \(G\) whose vertices include every vertex of \(T\).

(Gale, 1957.) Let \(N\) be a network with source set \(X\), sink set \(Y\), and capacity function \(c\), and suppose each vertex \(x\) is assigned a non-negative integer supply \(\sigma (x)\) and each vertex \(y\) a non-negative integer demand \(\partial (y)\). Then \(N\) admits a feasible flow for the supplies \(\sigma \) and demands \(\partial \) if and only if, for every vertex set \(S\),

where \(\bar S\) denotes the complement of \(S\) and \(\mathrm{cap}(S,\bar S)\) is the capacity of the cut from \(S\) to \(\bar S\).

Let \(p=(p_1,\dots ,p_m)\) and \(q=(q_1,\dots ,q_n)\) be sequences of non-negative integers with equal total, \(\sum _{i=1}^{m} p_i = \sum _{j=1}^{n} q_j\), and suppose \(q\) is non-increasing, \(q_1 \ge q_2 \ge \cdots \ge q_n\). Then \((p,q)\) is realisable by a simple bipartite graph if and only if

Let \(p_0, p_1, \ldots , p_m\) and \(q_0, q_1, \ldots , q_{n-1}\) be nonnegative integers, regarded as prescribed row degrees and column degrees. Then the pair \((p, q)\) is realisable by a simple bipartite graph if and only if the reduced pair \((p', q')\) is realisable, where \(p' = (p_1, \ldots , p_m)\) is obtained by deleting the first row degree \(p_0\), and the reduced column degrees are

that is, one is subtracted (never below zero) from each of the first \(p_0\) column degrees and the remaining column degrees are left unchanged.

Let \(G\) be a finite simple graph that is \((m+n)\)-regular. Then \(G\) is \((m,n)\)-orientable — it admits an orientation in which every vertex has indegree \(m\) or \(n\) — if and only if the vertex set can be split into two disjoint sets \(V_1\) and \(V_2\) whose union is the whole vertex set, such that for every set \(S\) of vertices

where \(\left\lvert [S,\bar S]\right\rvert \) is the number of edges of \(G\) with one end in \(S\) and the other outside \(S\).

Let \(G\) be a finite \((m+n)\)-regular simple graph, and suppose \(n \lt m\). If \(G\) is \((m,n)\)-orientable — that is, its edges admit an orientation in which every vertex has indegree equal to \(m\) or to \(n\) — then \(G\) is also \((m-1,\, n+1)\)-orientable.