e when nodes and links potentially affect the overall cost and performance of the network. One way that links can be essential is if they provide the only connections between nodes, or even more importantly, between distinct subnetworks. This latter property corresponds to the idea of a connected graph in graph theory. A graph is said to be connected if it cannot be split up into two disjoint graphs. Equivalently, a graph is connected if any pair of nodes is connected by a path, which is a sequence that consists of connected but distinct nodes and links. If a network can be split up into distinct subnetworks, the connected subnetworks sometimes are referred to as components in graph theory. There are two measures of how connected a graph is. One measure is to remove nodes to see whether the remaining graph is still connected. A graph G with at least k + 1 nodes is k-connected if it is still connected after k - 1 or fewer nodes are removed. The other measure is to remove links to see whether the remaining graph is still connected. A graph G is said to be k-link-connected if it is still connected after k - 1 or fewer links are removed. Even if a graph is k-connected, links need not be redundant. Rather, extra links provide reliability if some links fail to function properly. Also, extra links add capacity, SO that links need not be considered duplicates. Some links are needed for additional capacity if traffic flows are not uniform or if those links provide backbone transmission that is distinct from lower-volume transmission to and from terminal nodes. For more precise definitions, see Wilson and Beineke (1979). The Design and Costs of Networks Four of these Four of these Four of these Four of these Figure 2.2. There are sixteen minimum spanning trees in a graph with four nodes. 2. Cost-Minimizing Network Design A standard approach to network design is to begin with a set of nodes and to imagine all possible links between those nodes. With n nodes, there are n(n - 1) links in a complete graph. Then consider the co