Unit 4: Connectivity, Cut-Sets, Fundamental Circuits & Menger's Theorem

1. Cut-Vertices and Articulation Points

Definition 4.1 (Cut-Vertex): A vertex $v \in V(G)$ in a connected graph $G$ is called a cut-vertex (or articulation point) if its removal strictly increases the number of connected components:

where $G - v$ is the graph obtained by deleting vertex $v$ and all edges incident with $v$.

Theorem 4.1 (Characterization of Cut-Vertices): Let $G$ be a connected graph. A vertex $v \in V(G)$ is a cut-vertex if and only if there exist two distinct vertices $u, w \in V(G) \setminus \{v\}$ such that every path connecting $u$ and $w$ passes through $v$.

Proof:

• $(\implies)$ Suppose $v$ is a cut-vertex. Then $G - v$ is disconnected, so there exist two vertices $u, w \in V(G - v)$ that belong to different connected components of $G - v$.

Therefore, there is no $u$-$w$ path in $G - v$. However, since $G$ was connected, there was a $u$-$w$ path in $G$. Since this path cannot exist in $G - v$, it must pass through vertex $v$. Hence every $u$-$w$ path in $G$ must pass through $v$.

• $(\impliedby)$ If every $u$-$w$ path passes through $v$, then removing $v$ destroys all $u$-$w$ paths, leaving $u$ and $w$ disconnected in $G - v$.

Thus $\omega(G - v) \ge 2$, meaning $v$ is a cut-vertex. $\blacksquare$

2. Bridges (Cut-Edges)

Definition 4.2 (Bridge / Cut-Edge): An edge $e \in E(G)$ in a connected graph $G$ is called a bridge (or cut-edge) if its removal disconnects the graph:

Theorem 4.2 (Cycle-Edge Characterization of Bridges): An edge $e \in E(G)$ is a bridge if and only if $e$ does NOT belong to any cycle in $G$.

Proof:

• $(\implies)$ Suppose $e = \{u, v\}$ is a bridge. Then $G - e$ has no $u$-$v$ path.

If $e$ belonged to some cycle $C$, then $C - e$ would provide an alternative $u$-$v$ path in $G - e$, contradicting that $G - e$ is disconnected. Thus $e$ cannot lie on any cycle.

• $(\impliedby)$ Suppose $e = \{u, v\}$ is not a bridge. Then $G - e$ remains connected, so there exists a $u$-$v$ path $P$ in $G - e$.

Then $P \cup \{e\}$ forms a simple cycle in $G$ containing $e$. $\blacksquare$

3. Blocks and Non-Separable Graphs

Definition 4.3 (Block): A connected graph is non-separable if it has order $\ge 3$ and contains no cut-vertices. A block of a graph $G$ is a maximal non-separable connected subgraph. Two blocks of $G$ intersect in at most one vertex (which must be a cut-vertex of $G$).

1. Cut-Sets and Edge Separators

Definition 4.4 (Cut-Set): A cut-set $S \subseteq E(G)$ in a connected graph $G$ is a minimal set of edges whose removal disconnects $G$:

1. $\omega(G - S) > 1$.
2. For any proper subset $S' \subsetneq S$, $\omega(G - S') = 1$ (minimality).

A cut-set partitions the vertex set $V$ into two disjoint non-empty subsets $V_1, V_2$ ($V_1 \cup V_2 = V$) such that $S$ consists of all edges having one endpoint in $V_1$ and one in $V_2$, denoted $S = [V_1, V_2]$.

2. Fundamental Circuits Relative to a Spanning Tree

Let $T$ be a spanning tree of a connected graph $G = (V, E)$.

• The edges of $T$ are called branches. There are $n - 1$ branches.
• The edges in $E \setminus E(T)$ are called chords (or links). There are $m - (n - 1) = \mu(G)$ chords, where $\mu(G) = m - n + 1$ is the circuit rank (cyclomatic number) of $G$.

Definition 4.5 (Fundamental Circuit): Adding any chord $e \in E \setminus E(T)$ to $T$ produces a unique cycle, called the fundamental circuit associated with chord $e$, denoted $C(e)$. The set of all $\mu(G) = m - n + 1$ fundamental circuits forms a basis for the cycle space of $G$.

3. Fundamental Cut-Sets Relative to a Spanning Tree

Definition 4.6 (Fundamental Cut-Set): Removing any branch $b \in E(T)$ from $T$ splits $T$ into two trees $T_1$ and $T_2$ on vertex sets $V_1$ and $V_2$. The cut-set $[V_1, V_2]$ in $G$ contains the branch $b$ and some set of chords, but no other branches of $T$. This cut-set is called the fundamental cut-set associated with branch $b$, denoted $S(b)$. There are exactly $n - 1$ fundamental cut-sets, forming a basis for the cut space of $G$.

Theorem 4.3 (Ring Sum / Intersection Orthogonality): Every cut-set and every cycle in a graph share an even number of edges:

Proof:

Let $S = [V_1, V_2]$ be a cut-set. As a cycle $C$ traverses its vertices, every time it crosses from $V_1$ to $V_2$ it uses an edge in $S$. Since $C$ is a closed walk, to return to its initial vertex, the number of crossings from $V_1$ to $V_2$ must equal the number of crossings from $V_2$ to $V_1$. Thus the total number of edges in $E(C) \cap S$ is twice the number of transitions from $V_1$ to $V_2$, which is an even integer. $\blacksquare$

1. Vertex Connectivity $\kappa(G)$ and Edge Connectivity $\lambda(G)$

Definition 4.7 (Vertex Connectivity $\kappa(G)$): The vertex connectivity (or connectivity) of a graph $G$, denoted $\kappa(G)$, is the minimum number of vertices whose removal disconnects $G$ or reduces it to a trivial graph $K_1$. For the complete graph $K_n$, $\kappa(K_n) = n - 1$. A graph is $k$-connected if $\kappa(G) \ge k$.

Definition 4.8 (Edge Connectivity $\lambda(G)$): The edge connectivity of a graph $G$, denoted $\lambda(G)$, is the minimum number of edges whose removal disconnects $G$. $\lambda(G) = \min \{ |S| : S \text{ is a cut-set of } G \}$. A graph is $k$-edge-connected if $\lambda(G) \ge k$.

2. Whitney's Inequality Theorem

In 1932, Hassler Whitney established the fundamental inequality relating vertex connectivity, edge connectivity, and minimum degree:

Theorem 4.4 (Whitney's Inequality, 1932): For every graph $G$:

where $\delta(G)$ is the minimum degree of $G$.

Complete Formal Proof:

1. Proof of $\lambda(G) \le \delta(G)$:

Let $v \in V(G)$ be a vertex of minimum degree: $\deg(v) = \delta(G)$. Removing all $\delta(G)$ edges incident with $v$ isolates vertex $v$ from the rest of the graph (assuming $n \ge \delta + 1$). Thus the set of edges incident with $v$ forms an edge-cut of size $\delta(G)$. By definition of edge connectivity as the minimum size of an edge-cut:

2. Proof of $\kappa(G) \le \lambda(G)$:

• If $\lambda(G) = 0$, $G$ is disconnected, so $\kappa(G) = 0 \le 0$.
• If $\lambda(G) = 1$, $G$ contains a bridge $e = \{u, v\}$.
• If $n = 2$, $G = K_2$, so $\kappa(G) = 1 = \lambda(G)$.
• If $n > 2$, at least one of $u$ or $v$ has degree $\ge 2$. Removing that vertex disconnects the graph, so $\kappa(G) = 1 \le 1$.
• Now assume $\lambda(G) = k \ge 2$.

Let $E_{\text{cut}} = \{e_1, e_2, \dots, e_k\}$ be a minimum edge-cut of size $k = \lambda(G)$. Removing $E_{\text{cut}}$ partitions $V$ into two connected components $V_1$ and $V_2$.

• Case A: Every vertex in $V_1$ is adjacent to every vertex in $V_2$.

Then $|E_{\text{cut}}| = |V_1| \cdot |V_2|$. Since $|E_{\text{cut}}| = k$ and $|V| = |V_1| + |V_2| \ge |V_1| \cdot |V_2| + 1$ (unless one set has size 1): Removing $V_1$ leaves $V_2$ disconnected from $V_1$. The number of vertices in $V_1$ is $|V_1| \le |V_1||V_2| = k$. Thus removing $|V_1|$ vertices isolates or destroys the graph, so $\kappa(G) \le |V_1| \le k = \lambda(G)$.

• Case B: There exist $u \in V_1$ and $w \in V_2$ such that $\{u, w\} \notin E(G)$.

Construct a vertex set $U$ by taking: For each edge $e_i \in E_{\text{cut}}$, pick its endpoint in $V_1$ (if not equal to $u$), or pick its endpoint in $V_2$ (if not equal to $w$). The set $U$ has size $|U| \le |E_{\text{cut}}| = k$. Notice that $u \notin U$ and $w \notin U$. Any $u$-$w$ path in $G$ must use at least one edge in $E_{\text{cut}}$. Because $U$ contains at least one endpoint of every edge in $E_{\text{cut}}$, deleting $U$ destroys all paths between $u$ and $w$! Therefore, $u$ and $w$ lie in different components of $G - U$. Thus $U$ is a vertex-cut, which implies:

Combining both inequalities yields $\kappa(G) \le \lambda(G) \le \delta(G)$. $\blacksquare$

1. Internally Disjoint Paths

Definition 4.9 (Internally Disjoint Paths): Two $u$-$v$ paths $P_1$ and $P_2$ in a graph $G$ are internally disjoint (or vertex-disjoint) if they share no vertices other than their common endpoints $u$ and $v$:

They are edge-disjoint if they share no edges: $E(P_1) \cap E(P_2) = \emptyset$.

2. Menger's Theorem (Karl Menger, 1927)

One of the deepest minimax theorems in combinatorics, establishing the duality between maximum disjoint paths and minimum separating sets:

Theorem 4.5 (Menger's Theorem — Vertex Form): Let $u$ and $v$ be distinct non-adjacent vertices in a graph $G$. The maximum number of pairwise internally disjoint $u$-$v$ paths is equal to the minimum number of vertices whose removal disconnects $u$ and $v$:

Theorem 4.6 (Menger's Theorem — Edge Form): Let $u$ and $v$ be distinct vertices in a graph $G$. The maximum number of pairwise edge-disjoint $u$-$v$ paths is equal to the minimum number of edges whose removal disconnects $u$ and $v$:

3. Global Menger Characterizations of $k$-Connectivity

Corollary 4.5.1 (Global Vertex Connectivity): A graph $G$ on $n \ge k + 1$ vertices is $k$-connected ($\kappa(G) \ge k$) if and only if every pair of distinct vertices is connected by at least $k$ internally disjoint paths.

Corollary 4.5.2 (Global Edge Connectivity): A graph $G$ is $k$-edge-connected ($\lambda(G) \ge k$) if and only if every pair of distinct vertices is connected by at least $k$ edge-disjoint paths.

1. Separable Graphs and Cut-Vertices

Definition 4.10 (Separable Graph): A connected graph is separable if it has at least one cut-vertex (i.e., its vertex connectivity $\kappa(G) = 1$). A graph of connectivity $\kappa(G) \ge 2$ is called non-separable.

2. 1-Isomorphism and 2-Isomorphism

Can two graphs have identical circuit/cycle structures without being strictly isomorphic? Hassler Whitney formulated structural relaxations:

Definition 4.11 (1-Isomorphism): Two graphs $G_1$ and $G_2$ are 1-isomorphic if $G_2$ can be obtained from $G_1$ by:

1. Splitting a cut-vertex into two vertices (separating blocks).
2. Gluing two separate component vertices together into a single cut-vertex.

Definition 4.12 (2-Isomorphism): Two graphs $G_1$ and $G_2$ are 2-isomorphic if $G_2$ can be obtained from $G_1$ by a sequence of 1-isomorphisms and vertex twisting operations:

• Vertex Twisting: If $\{u, v\}$ is a 2-vertex cut separating $G$ into two subgraphs $G_A$ and $G_B$ meeting only at $\{u, v\}$, detach $G_B$ and reattach it with the roles of $u$ and $v$ swapped!

Theorem 4.7 (Whitney's 2-Isomorphism Theorem, 1933): Two graphs $G_1$ and $G_2$ have isomorphic cycle spaces (i.e., there is an edge bijection preserving all circuits) if and only if $G_1$ and $G_2$ are 2-isomorphic. Furthermore, if $G_1$ is 3-connected, then any 2-isomorphism is an authentic isomorphism!