Chapter 4: Connectivity and Paths

Source: Introduction to Graph Theory, 2nd Edition, by Douglas B. West

Overview

Chapter 4 studies how well-connected a graph is, addressing the fundamental question of how difficult it is to disrupt a communication network. The chapter develops three interrelated topics: the basic notions of vertex and edge connectivity (Section 4.1), the deeper structural theory of k-connected graphs centered on Menger's Theorem (Section 4.2), and the algorithmic framework of network flow that provides computational tools and proves the key duality results (Section 4.3). Throughout the chapter, graphs and digraphs are assumed to have no loops.

4.1 Cuts and Connectivity

Connectivity (Vertex Connectivity)

Definition 4.1.1 — Separating set / vertex cut: A set S of vertices in G such that G − S has more than one component. The connectivity κ(G) is the minimum size of a vertex cut (or one less than the order if G is complete). A graph is k-connected if its connectivity is at least k.
Example 4.1.2: κ(K_n) = n − 1; κ(K_m,n) = min{m, n}. For instance, K_3,3 has connectivity 3.
Example 4.1.3 — Hypercubes: κ(Q_k) = k, proved by induction on k. Every vertex cut of Q_k has size at least k.
Example 4.1.4 — Harary graphs: H_k,n achieves exactly connectivity k with the minimum number of edges. Vertices are placed on a circle and connected to the nearest k/2 in each direction.
Theorem 4.1.5 (Harary, 1962): κ(H_k,n) = k, and the minimum number of edges in a k-connected graph on n vertices is ⌈kn/2⌉.

Edge-Connectivity

Definition 4.1.7 — Disconnecting set / edge cut: A set F of edges such that G − F has more than one component. The edge-connectivity κ'(G) is the minimum size of a disconnecting set. An edge cut has the form [S, S̄] for a nonempty proper subset S of V(G).
Remark 4.1.8: Every edge cut is a disconnecting set, but the converse is false. However, every minimal disconnecting set is an edge cut.
Theorem 4.1.9 (Whitney, 1932): For any simple graph G, κ(G) ≤ κ'(G) ≤ δ(G). This fundamental inequality relates connectivity, edge-connectivity, and minimum degree.
Example 4.1.10: The three parameters can all differ: there exist graphs with κ = 1, κ' = 2, δ = 3.
Theorem 4.1.11: For 3-regular graphs, κ(G) = κ'(G).
Proposition 4.1.12: |[S, S̄]| = sum of degrees in S minus 2 times the edges within S. This gives a formula for computing edge cut sizes.
Corollary 4.1.13: If |[S, S̄]| < δ(G) for some nonempty proper S, then |S| > δ(G).
Definition 4.1.14 — Bond: A minimal nonempty edge cut.
Proposition 4.1.15: In a connected graph, an edge cut F is a bond if and only if G − F has exactly two components.

Blocks

Definition 4.1.16 — Block: A maximal connected subgraph of G with no cut-vertex. Blocks with more than two vertices are 2-connected.
Example 4.1.17: A graph decomposes into blocks: its isolated vertices, cut-edges, and maximal 2-connected subgraphs.
Remark 4.1.18: Blocks of a loopless graph are its isolated vertices, cut-edges, and maximal 2-connected subgraphs. Two blocks share at most one vertex (Proposition 4.1.19).
Definition 4.1.20 — Block-cutpoint graph: A bipartite graph with one partite set being the cut-vertices and the other the blocks of G, with edges indicating containment. When G is connected, this is a tree.
Depth-First Search (DFS): Introduced as a technique for finding blocks, exploring from the most recently discovered vertex (backtracking). Contrasted with BFS which explores from the oldest vertex.
Lemma 4.1.22: In a DFS spanning tree T, every non-tree edge connects an ancestor to a descendant.
Algorithm 4.1.23: An algorithm to compute blocks of a graph using DFS, discarding portions of the DFS tree as blocks are identified.

4.2 k-Connected Graphs

2-Connected Graphs

Definition 4.2.1 — Internally disjoint paths: Two paths from u to v are internally disjoint if they share no internal vertex.
Theorem 4.2.2 (Whitney, 1932): A graph with at least 3 vertices is 2-connected if and only if every pair of vertices is connected by internally disjoint paths. The proof uses induction on the distance d(u, v).
Lemma 4.2.3 — Expansion Lemma: Adding a vertex y with at least k neighbors to a k-connected graph produces a k-connected graph.
Theorem 4.2.4: Four equivalent characterizations of 2-connected graphs (for graphs with at least 3 vertices):
- (A) Connected with no cut-vertex
- (B) Internally disjoint x,y-paths exist for all x, y
- (C) A cycle through x and y exists for all x, y
- (D) δ(G) ≥ 1 and every pair of edges lies on a common cycle
Definition 4.2.5 — Subdivision: Replacing an edge uv with a path u, w, v through a new vertex w.
Corollary 4.2.6: Subdividing an edge of a 2-connected graph preserves 2-connectedness.

Ear Decomposition

Definition 4.2.7 — Ear: A maximal path whose internal vertices have degree 2. An ear decomposition is P₀, P₁, ..., P_t where P₀ is a cycle and each subsequent P_i is an ear of P₀ ∪ ... ∪ P_i.
Theorem 4.2.8 (Whitney, 1932): A graph is 2-connected if and only if it has an ear decomposition. Every cycle in a 2-connected graph is the initial cycle of some ear decomposition.
Definition 4.2.9 — Closed ear: A cycle C where all vertices except one have degree 2. A closed-ear decomposition allows each P_i to be either an open or closed ear.
Theorem 4.2.10: A graph is 2-edge-connected if and only if it has a closed-ear decomposition, and every cycle can be the initial cycle.

Connectivity of Digraphs

Definition 4.2.11: Separating sets, vertex cuts, k-connectivity, edge cuts, and k-edge-connectivity are defined for digraphs in terms of strong connectivity.
Remark 4.2.12: A graph or digraph is k-edge-connected iff every nonempty proper vertex subset S has at least k edges leaving it.
Proposition 4.2.13: Adding a directed ear to a strong digraph yields a larger strong digraph.
Theorem 4.2.14 (Robbins, 1939): A graph has a strong orientation if and only if it is 2-edge-connected. The proof uses closed-ear decomposition.

k-Connected and k-Edge-Connected Graphs

Definition 4.2.15: Given x, y ∈ V(G), an x, y-separator (or x, y-cut) is a set S ⊆ V(G) − {x, y} such that G − S has no x, y-path. κ(x, y) is the minimum size of an x, y-cut. λ(x, y) is the maximum number of pairwise internally disjoint x, y-paths. An X, Y-path starts in X, ends in Y, and has no other vertex in X ∪ Y.
Example 4.2.16: Demonstrates that κ(x, y) = λ(x, y) on a specific graph, illustrating Menger's Theorem.

Menger's Theorem

Theorem 4.2.17 (Menger, 1927): If x, y are vertices of a graph G and xy is not an edge, then the minimum size of an x, y-cut equals the maximum number of pairwise internally disjoint x, y-paths. This is one of the most important theorems in graph theory. The proof uses induction on n(G), with two cases depending on whether the minimum cut is or is not N(x) or N(y).
Definition 4.2.18 — Line graph: L(G) is the graph whose vertices are the edges of G, with adjacency when two edges share an endpoint. Used to convert edge-disjoint path problems to internally disjoint path problems.
Theorem 4.2.19 (Edge version of Menger's Theorem): The minimum size of an x, y-disconnecting set of edges equals the maximum number of pairwise edge-disjoint x, y-paths. Proved by transforming to L(G) and applying Theorem 4.2.17.
Lemma 4.2.20: Deleting an edge reduces connectivity by at most 1.
Theorem 4.2.21 (Global Menger's Theorem): The connectivity of G equals the maximum k such that λ(x, y) ≥ k for all x, y ∉ E(G). The edge-connectivity equals the maximum k such that λ'(x, y) ≥ k for all x, y. Both hold for graphs and digraphs.

Applications of Menger's Theorem

Definition 4.2.22 — Fan: Given vertex x and set U, an x, U-fan is a set of paths from x to U sharing only x pairwise.
Theorem 4.2.23 (Fan Lemma, Dirac 1960): G is k-connected iff for every x and every U with |U| ≥ k, there is an x, U-fan of size k.
Theorem 4.2.24 (Dirac, 1960): In a k-connected graph, any set of k vertices lies on a common cycle.
Theorem 4.2.25 (Ford–Fulkerson, 1958): Characterizes when two families of sets A and B have a common system of distinct representatives (CSDR), proved using Menger's Theorem on an appropriate digraph.

4.3 Network Flow Problems

Basic Definitions

Definition 4.3.1 — Network: A digraph with nonnegative capacity c(e) on each edge, a source s, and a sink t. A flow f assigns a value f(e) to each edge satisfying capacity constraints (0 ≤ f(e) ≤ c(e)) and conservation constraints (flow in = flow out at every non-source/sink node).
Definition 4.3.2: The value val(f) of a flow is f⁻(t) − f⁺(t), the net flow into the sink. A maximum flow has maximum value.

Augmenting Paths

Definition 4.3.4 — f-augmenting path: A source-to-sink path P in the underlying graph such that forward edges have excess capacity and backward edges have positive flow. The tolerance is the minimum slack along P.
Lemma 4.3.5: Augmenting along an f-augmenting path with tolerance z produces a feasible flow of value val(f) + z.

Cuts and Duality

Definition 4.3.6 — Source/sink cut: [S, T] partitions V(N) with s ∈ S and t ∈ T. The capacity cap(S, T) is the total capacity on edges from S to T.
Lemma 4.3.7: For any set U of nodes, the net flow out of U is the sum of net flows of the individual nodes. In particular, for a source/sink cut [S, T], the net flow out of S equals val(f).
Corollary 4.3.8 (Weak duality): val(f) ≤ cap(S, T) for any feasible flow f and any source/sink cut [S, T].

Ford–Fulkerson Algorithm

Algorithm 4.3.9 (Ford–Fulkerson labeling algorithm): Starting from a feasible flow, iteratively search for f-augmenting paths using a labeling procedure. If t is reached, augment the flow. If t is not reached, the labeled set S and unlabeled set T form a minimum cut.
Theorem 4.3.11 (Max-flow Min-cut Theorem, Ford–Fulkerson 1956): In every network, the maximum value of a feasible flow equals the minimum capacity of a source/sink cut. This is one of the foundational results in combinatorial optimization. The proof requires rational capacities; Edmonds and Karp (1972) modified the algorithm to work for all real capacities by always choosing shortest augmenting paths.

Integral Flows

Corollary 4.3.12 (Integrality Theorem): If all capacities are integers, there exists a maximum flow assigning integral flow to each edge, and it can be decomposed into flows of unit value along paths from source to sink.
Remark 4.3.13 — Menger from Max-flow Min-cut: With unit capacities, the Max-flow Min-cut Theorem directly yields Menger's Theorem for edge-disjoint paths in digraphs. A flow of value k corresponds to k edge-disjoint paths.
Remark 4.3.14 — Max-flow Min-cut from Menger: Conversely, Menger's Theorem implies the Max-flow Min-cut Theorem for rational capacities.
Remark 4.3.15 — Other transformations: Network models for internally disjoint paths (split each vertex v into v⁻ and v⁺ with a unit-capacity edge) and for edge-disjoint paths in undirected graphs (replace each edge with two directed edges).

Applications

Application 4.3.16 — Baseball Elimination Problem (Schwartz, 1966): Uses network flow to determine whether a team can still win the championship. A network is constructed with team nodes, pair nodes, source, and sink, with capacities encoding remaining games and win limits.
Theorem 4.3.17 (Gale, 1957): A feasible flow exists in a transportation network (multiple sources and sinks with supplies and demands) iff c([S̄, T]) ≥ ∂(Y ∩ T) − σ(X ∩ T) for every partition S, T.
Theorem 4.3.18 (Gale–Ryser, 1957): Characterizes when a pair of degree lists (p, q) is bigraphic (realizable as a bipartite graph), proved via network flow.
Application 4.3.19 — Matrix Rounding (Bacharach, 1966): Consistent rounding of a real matrix to integers while preserving row and column sums, modeled as a feasible flow problem.

Circulations and Lower Bounds

Solution 4.3.20 — Circulations with lower bounds: For networks with both lower and upper bounds on edge flows, feasibility is tested by converting to a standard max-flow problem. A circulation is a flow with conservation at every node (no source or sink).
Corollary 4.3.21: A circulation with lower and upper bounds is feasible iff the cut condition (sum of lower bounds ≤ sum of upper bounds) holds for every vertex subset S.

Key Themes and Significance

The κ ≤ κ' ≤ δ inequality (Whitney's Theorem 4.1.9) establishes the hierarchy of connectivity measures and shows that vertex connectivity is the strongest notion of connection.
Menger's Theorem (4.2.17) is the central result of the chapter, equating the minimum number of vertices needed to disconnect two vertices with the maximum number of internally disjoint paths between them. It unifies vertex connectivity, edge connectivity, and path structure.
The Max-flow Min-cut Theorem (4.3.11) is the algorithmic counterpart to Menger's Theorem, providing both a computational method (Ford–Fulkerson algorithm) and a duality framework. The equivalence between Menger's Theorem and Max-flow Min-cut (Remarks 4.3.13–4.3.14) shows these are different views of the same phenomenon.
Structural characterizations of 2-connected graphs (Whitney's Theorem 4.2.2, ear decomposition 4.2.8) and 2-edge-connected graphs (closed-ear decomposition 4.2.10) provide constructive ways to understand connectivity.
Applications demonstrate the broad utility of network flow: baseball elimination, transportation problems, matrix rounding, testing bigraphic degree sequences, and proving combinatorial existence theorems via the Integrality Theorem.

Key Theorems and Results

Result	Statement
Whitney (4.1.9)	κ(G) ≤ κ'(G) ≤ δ(G)
Whitney (4.2.2)	G is 2-connected ⟺ every pair has internally disjoint paths
Ear Decomposition (4.2.8)	G is 2-connected ⟺ G has an ear decomposition
Robbins (4.2.14)	G has a strong orientation ⟺ G is 2-edge-connected
Menger (4.2.17)	Min x,y-cut = max internally disjoint x,y-paths
Fan Lemma (4.2.23)	G is k-connected ⟺ x,U-fans of size k exist
Dirac (4.2.24)	In a k-connected graph, any k vertices lie on a common cycle
Max-flow Min-cut (4.3.11)	Max flow value = min cut capacity
Integrality Theorem (4.3.12)	Integer capacities ⟹ integer max flow exists
Gale–Ryser (4.3.18)	Characterization of bigraphic degree sequences via network flow

Flags

Introduction to Graph Theory/Connectivity and Paths

From charlesreid1

Contents