 at that level.³ Although a formal proof of the max-flow/min-cut theorem exceeds the scope of this book, the basic intuitions underlying it can be easily explained in a relatively nontechnical manner. The theorem focuses on the maximum flow capacity of a network transporting traffic from a source (usually denoted s) to a destination called a sink (usually denoted t). 4 A cut is a set of links that, if removed, divide the graph into two subgraphs. The two subgraphs contain distinct sets of nodes. Of greatest relevance, for our purposes, are those cuts in which the source (node s) and the sink (node t) lie in different sets. The set of nodes containing the source node S is typically called S, and the set of nodes containing the sink node t is typically called T. The key insight is that any traffic bound from node S to node t necessarily must travel from nodes contained in set S to nodes contained in set T and hence along the links in the cut. As a result, the total carrying capacity of the links directly connecting one of the nodes in set S to nodes in set T represents a constraint on the total carrying capacity of the network. This theorem is prominently discussed in most graph theory texts. For a relatively accessible exposition, see Stein (2004). The network is portrayed as a one-way network from a single source to a single sink. Certain aspects of this simplification do not affect the generality of the analysis. For example, the insights provided by the analysis of t networks can be extended to networks with multiple sources and multiple sinks without any loss of generality (Wallis 2000). In addition, the foregoing exposition focuses solely on the capacity of links without taking into account the capacity limits on nodes. A node with a capacity constraint can be reconceptualized as two uncapacitated nodes connected by a capacity-constrained link. As a result, the entire analysis can focus solely on the capacity of links without loss of generality. Other aspects are potentially more problematic. The most signifi