Technical Terms:
adjacent, arc, arc disjoint, block, bridge, connected, cutedge, cutnode, cycle, disjoint, edge-disjoint, nonseparable, path, separate, subgraph, subpath, walk.
Removal of a node (and all edges incident to it) from a graph can increase its number of components. So can the removal of an edge (but not the two nodes incident to it). Some terminology is useful. That used here is due to Harary (1969).
Examples
and
and
and
Theorem 4c.1. Let G be a connected graph. Then v is a cutnode of G if and only if G - {v} can be partitioned into subsets U and W such that v is a node on every path from a node of U to a node of W.
Proof:
⇒ Suppose v is a cutnode of G. Then G - {v} contains at least two components. Let U be the set of nodes of one component, W be the set of the remaining nodes of G - {v}. Then, if u∈U and w∈W, u and w are in different components. Hence, there is no path from u to w in G - {v}. So any path from u to w in G must contain v.
⇐ Suppose a partition of G - {v} exists. Then let u∈U, w∈W. There is no path from u to w in G - {v}. So G - {v} is not connected. Hence, v is a cutnode of G.
Theorem 4c.2. (Equivalent Conditions for Bridges). Let G be a connected graph. Then the following conditions are equivalent.
Proof:
(1) ⇒ (2) If e is a bridge, e cannot be a cycle, or its removal would not disconnect G, since any path in G containing e could be replaced in G - e by a path containing the rest of the cycle.
(2) ⇒ (3) analogous to ⇒ of Theorem 4c.1.
(3) ⇒ (2) analogous to ⇐ of Theorem 4c.1.
Theorem 4c.3. (Equivalent Conditions for Blocks). Let G be a connected graph with at least three nodes. Then the following conditions are equivalent.
Proof:
(1) ⇒ (2)
Suppose u, v are two different nodes of G. Let U be the set of nodes in G - {u} that lie on a cycle containing u. The block G has no bridges, since G has no cutnodes and at least three nodes. Therefore, every node adjacent to u is in U. Thus, U ≠ Ø. Now suppose v∉ U. Let w be a node in U at minimum distance from v, P the path from w to v of this minimum length.
There is a path P' from u to v not containing w, since w is not a cutnode. Let w' be the node nearest u in P' and also in P. Let u' be the last node of the subpath from u to w' which is also on a common cycle containing u and w. Let P1 be the path from u to w containing u', and let P2 be the other path from u to w comprising the rest of this common cycle.
Let Q1 be the u - w' path consisting of the u - u' subpath of P1 and the u' - w' subpath of P'. Let Q2 be the u - w' path consisting of P2 followed by the w - w' subpath of P. Q1 and Q2 together form a cycle, so w' is in U. But w' lies on P, so d(w',v)<d(w,v), contradicting the choice of w.
Thus, u and v lie on a common cycle.
(2) ⇒ (3) Let u be a node, vw an edge. There is a cycle C1 containing u and v. The proof is done unless w is not in this cycle. There is a cycle C2 containing w and u. Choose a u - v subpath of C1 followed by vw followed by a w - u subpath of C2 to get a closed walk containing u and vw. Remove edges (if necessary) to get the desired cycle.
(3) ⇒ (4) Let e, f be two edges.
Case 1 e = uv, f = vw.
Case 2 e = uv, f = wx.
(4) ⇒ (1)
Let v be a node. Let u, w be nodes for which there is a u - w path containing v. By (4) they lie on a common cycle. So there is a u - w path not containing v. Since u, w where chosen arbitrarily, v is not a cutnode.
Thus, G is a block.
If v is a cutnode of a connected graph G, then it separates two nodes in different components of G - v, in the sense that any path between such nodes must contain v. A similar situation exists when several nodes must be removed to separate two nodes.
First, a little terminology is needed. Two paths from u to v are said to be disjoint if they have no nodes or edges in common except u and v. If they have no edges in common, they are called edge-disjoint. A set S of nodes is said to separate u and v if u and v are in different components of G - S.
Theorem 4c.4 (Menger, 1927). Let S be a minimal set of nodes in G separating two non-adjacent nodes u and v. If S has n elements, then the maximum number of disjoint u - v paths is n.
Proof: (Dirac, 1966). Clearly, there can be no more than n disjoint paths joining u and v, one for each element in S. It must be shown that n disjoint paths do exist. If n = 1, then S = {x}, x is a cutnode, and any path from u to v contains x. So no two such paths are disjoint.
Suppose that the theorem is untrue for some value of n, n>1. Let m be the smallest such n, and let G be a graph with the minimum number of nodes for which the theorem fails with |S| = m. Remove edges from G until a graph H is obtained such that m nodes are required to separate u and v in H, but for any edge e in H, only m - 1 nodes are required to separate u and v in H - e. To prove the theorem, it will be necessary to investigate the properties of H.
By definition of H, for any edge e of H, there is a set S(e) of m - 1 nodes which separates u and v in H - e. Now G - S(e) contains at least one u - v path, since it takes m≥1 nodes to separate u and v in H - e. Each such u - v path must contain e since it is not a path in H - e. Let e = st. Then s and t are not in S(e), and if s is not u or v, then S(e) ∪{s} separates u and v in G.
Claim 1 There is no node adjacent to both s and t in H.
For suppose there were. Then H - w requires m - 1 nodes to separate u and v and so has m - 1 disjoint u - w paths. Then u, w, v gives an mthu - v path in H, contradicting our assumption.
Claim 2 Let W be any collection of m nodes separating u and v in H. Then W is adjacent to either u or v.
Proof: Let a u - W path be any path joining u to a node of W but containing no other nodes of W. Call the collection of all u - W paths ℘u and of all W - v paths ℘v.
Each element of W is in at least one path in each of ℘u and ℘v . Further, no other node can be in both a u - W and a W - v path, since then there would be a u - v path containing no node of W, which separates u and v. Thus, the paths of ℘u and ℘v have exactly the nodes of W in common.
Finally, either ℘u - W = {u} or ℘v - W = {v}. Otherwise the graphs ℘u together with the set of edges {wv | w∈W} and ℘v together with the set of edges {uw | w∈W} are graphs with fewer edges than H in which u and v are separated by m nodes, in which case there are m disjoint u - v paths, contradicting our choice of H.
To complete the proof, let P = {u, s1, s2, ..., v} be a shortest u - v path in H, and let x = s1s2. By Claim 1, s2 ≠ v. Let S(x) = {t1, ..., th-1}, separating u and v in H - x. By Claim 1, u, v ∉ H. Let W = S(x) ∪ {u1}. Therefore by Claim 2 uti ∈ H for every i. Thus, by Claim 1, no ti v ∈ H. But picking W = S(x) ∪ {s1} instead gives us2 ∈ H, contradicting the choice of P as a shortest u - v path.
Now that Menger's Theorem has been proved, one can derive the Max-Flow Min-Cut Theorem of Chapter 3c as a corollary. First, we state a directed graph version of Menger's Theorem (Wilson, 1972). Just as a set of nodes can separate two nodes, so can a set of arcs.
Theorem 4c.5. The maximum number of arc-disjoint paths connecting two distinct nodes v and w of a digraph D is the minimum number of arcs in a set of arcs separating v and w.
Now we can prove:
Theorem 3c.6. Max-flow Min-cut Theorem. (Ford and Fulkerson, 1956). The value of the maximum flow through a network is equal to the capacity of a minimum cut.
Proof: Suppose, as mentioned in Chapter 3c, that the capacity of every arc is a non-negative integer. Then the network can be regarded as a multidigraph D' in which an arc x of capacity c(x) from a to b has been replaced by c(x) separate arcs from a to b.
Then the value of a maximum flow represents the total number of arc-disjoint paths from source v to sink w in D'. The capacity of a minimal cut has become the minimal number of arcs in a set of arcs separating v and w.
In that language, Theorem 3c.6 is just Theorem 4c.5.