COMPX270 — Chapter 5 Supplement
Mathematical Foundations: Graph Algorithms
Graph theory, edge contraction, conditional probability products, recurrence relations, MST properties, and counting arguments behind min-cuts and spanning trees.
Graph Theory Review
A graph is a pair \(G = (V, E)\) where \(V\) is a finite set of vertices and \(E\) is a set of edges. A multigraph allows parallel edges (multiple edges between the same pair of vertices) but no self-loops. In a multigraph, \(E\) is a multiset over \(\binom{V}{2}\).
The degree of a vertex \(v\), denoted \(\deg(v)\), is the number of edges incident to \(v\). In a multigraph, parallel edges each contribute separately to the degree.
For any graph (or multigraph) \(G = (V, E)\):
\[\sum_{v \in V} \deg(v) = 2|E|\]Each edge contributes exactly 2 to the total degree sum — one for each endpoint.
A cut in \(G = (V, E)\) is a partition of the vertex set into two non-empty subsets \((A, B)\) with \(A \cup B = V\) and \(A \cap B = \emptyset\). The cut edges (or cut-set) are:
\[\delta(A) = \bigl\{\{u, v\} \in E : u \in A,\; v \in B\bigr\}\]The size of the cut is \(|\delta(A)|\). A minimum cut (min-cut) is a cut of smallest size.
A graph is connected if there is a path between every pair of vertices. A spanning tree of a connected graph \(G = (V, E)\) is a subgraph \(T = (V, E')\) that is connected, acyclic, and spans all vertices. Every spanning tree has exactly:
\[|E'| = |V| - 1 \text{ edges}\]Min-Cut & Min-Degree
If \(G\) has a min-cut of size \(k\), then every vertex has degree at least \(k\). (Otherwise, the single vertex on one side would give a smaller cut.) By the handshaking lemma:
\[2|E| = \sum_{v \in V} \deg(v) \geq k \cdot |V| \implies |E| \geq \frac{k|V|}{2}\]Edge Contraction
Given a multigraph \(G = (V, E)\) and an edge \(e = \{u, v\}\), the contraction \(G/e\) is the multigraph obtained by:
- Merging \(u\) and \(v\) into a single new vertex \(w\).
- For every edge incident to \(u\) or \(v\) (other than \(e\) itself), reconnecting it to \(w\).
- Removing self-loops (edges that would connect \(w\) to itself) but keeping parallel edges.
The resulting multigraph has \(|V| - 1\) vertices.
Let \((A, B)\) be a cut in \(G\) such that both endpoints of \(e = \{u, v\}\) lie on the same side (i.e., \(u, v \in A\) or \(u, v \in B\)). Then \((A', B')\) in \(G/e\) (where the merged vertex \(w\) replaces \(u, v\) on their shared side) has exactly the same cut edges:
\[|\delta_{G/e}(A')| = |\delta_G(A)|\]In particular, if the min-cut of \(G\) does not separate \(u\) and \(v\), then the min-cut size is preserved in \(G/e\).
Multigraph Evolution during Karger's Algorithm
Karger's algorithm repeatedly contracts a uniformly random edge. After each contraction:
- The number of vertices decreases by exactly 1.
- Parallel edges accumulate — they represent multiple original edges between the "super-vertices."
- When only 2 vertices remain, the parallel edges between them form a candidate cut.
Starting from \(n\) vertices, the algorithm performs \(n - 2\) contractions.
Consider the triangle \(K_3\) with vertices \(\{a, b, c\}\) and edges \(\{ab, bc, ac\}\). Contracting edge \(ab\) merges \(a\) and \(b\) into a super-vertex \(w\). Both edges \(ac\) and \(bc\) become edges from \(w\) to \(c\), creating a multigraph with 2 vertices and 2 parallel edges. The resulting cut has size 2, which matches the min-cut of the original triangle.
Probability via Conditional Products
For events \(E_1, E_2, \ldots, E_n\):
\[\Pr[E_1 \cap E_2 \cap \cdots \cap E_n] = \prod_{i=1}^{n} \Pr[E_i \mid E_1 \cap \cdots \cap E_{i-1}]\]where \(\Pr[E_1 \mid \emptyset] = \Pr[E_1]\).
Application to Karger's Algorithm
Let \(E_i\) be the event "the \(i\)-th contraction does not destroy the min-cut." We want \(\Pr[E_1 \cap E_2 \cap \cdots \cap E_{n-2}]\). By the chain rule:
\[\Pr[\text{min-cut survives}] = \prod_{i=1}^{n-2} \Pr[E_i \mid E_1 \cap \cdots \cap E_{i-1}]\]After \(i - 1\) successful contractions, the multigraph has \(n - (i-1)\) vertices. If the min-cut has size \(k\), then every vertex has degree \(\geq k\), so by the handshaking lemma:
\[|E_i| \geq \frac{k(n - i + 1)}{2}\]Since at most \(k\) of these edges belong to the min-cut, the probability of picking a min-cut edge is at most:
\[\Pr[\text{bad}] \leq \frac{k}{\frac{k(n - i + 1)}{2}} = \frac{2}{n - i + 1}\]Therefore:
\[\Pr[E_i \mid E_1 \cap \cdots \cap E_{i-1}] \geq 1 - \frac{2}{n - i + 1} = \frac{n - i - 1}{n - i + 1}\]Multiplying all conditional probabilities:
\[\prod_{i=1}^{n-2} \frac{n - i - 1}{n - i + 1} = \frac{n-2}{n} \cdot \frac{n-3}{n-1} \cdot \frac{n-4}{n-2} \cdots \frac{2}{4} \cdot \frac{1}{3}\]This is a telescoping product. Rewriting with \(j = n - i + 1\) ranging from \(n\) down to \(3\):
\[\prod_{j=3}^{n} \frac{j - 2}{j} = \frac{1 \cdot 2}{(n-1) \cdot n} = \frac{2}{n(n-1)} = \frac{1}{\binom{n}{2}}\]For \(n = 4\), the product is:
\[\frac{2}{4} \cdot \frac{1}{3} = \frac{2}{12} = \frac{1}{6} = \frac{1}{\binom{4}{2}}\]confirming the formula.
Recurrence Relations
For recurrences of the form \(T(n) = a\,T(n/b) + O(n^d)\):
\[T(n) = \begin{cases} O(n^d) & \text{if } a < b^d \\ O(n^d \log n) & \text{if } a = b^d \\ O(n^{\log_b a}) & \text{if } a > b^d \end{cases}\]Karger–Stein Time Recurrence
The Karger–Stein algorithm contracts the graph from \(n\) vertices to \(n/\sqrt{2}\) vertices, then runs two independent copies on the reduced graph. The running time satisfies:
\[T(n) = 2\,T\!\left(\frac{n}{\sqrt{2}}\right) + O(n^2)\]Here \(a = 2\), \(b = \sqrt{2}\), \(d = 2\). Checking: \(b^d = (\sqrt{2})^2 = 2 = a\). So we are in the \(a = b^d\) case:
\[T(n) = O(n^2 \log n)\]where \(\log\) is base \(\sqrt{2}\), but since \(\log_{\sqrt{2}} n = 2\log_2 n = O(\log n)\), the result is \(O(n^2 \log n)\).
Probability Recurrence
Let \(p(n)\) be the probability that the Karger–Stein algorithm finds the min-cut. By contracting to \(n/\sqrt{2}\) vertices, each branch succeeds with probability at least \(1/2 \cdot p(n/\sqrt{2})\) (the factor \(1/2\) comes from the survival probability during contraction). Two independent trials give:
\[p(n) \geq 1 - \left(1 - \frac{p(n/\sqrt{2})}{2}\right)^2\]since failure requires both trials to fail.
Substitution Method
Let \(t = \log_{\sqrt{2}} n\), so \(n = (\sqrt{2})^t\). Define \(f(t) = p((\sqrt{2})^t)\). We guess \(f(t) \geq \frac{1}{t + c}\) for a suitable constant \(c\). The recurrence becomes:
\[f(t) \geq 1 - \left(1 - \frac{f(t-1)}{2}\right)^2 = f(t-1) - \frac{f(t-1)^2}{4}\]By induction with the ansatz \(f(t) \geq \frac{1}{t + 2}\), one verifies:
\[\frac{1}{t+1} - \frac{1}{4(t+1)^2} \geq \frac{1}{t+2}\]holds for \(t \geq 2\). Since \(t = O(\log n)\), we conclude:
\[p(n) = \Omega\!\left(\frac{1}{\log n}\right)\]Basic Karger: one trial has success probability \(1/\binom{n}{2} = \Theta(1/n^2)\). Need \(O(n^2)\) trials for constant success → total time \(O(n^4)\).
Karger–Stein: one trial has success probability \(\Omega(1/\log n)\). Need \(O(\log n)\) trials → total time \(O(n^2 \log^2 n)\), or \(O(n^2 \log^3 n)\) with boosting.
MST Properties
For any cut \((A, B)\) of a connected weighted graph \(G\), if edge \(e\) is the unique lightest edge crossing the cut, then \(e\) belongs to every minimum spanning tree (MST) of \(G\).
More generally, if \(e\) is a lightest crossing edge (possibly tied), then there exists an MST containing \(e\).
Let \(T\) be an MST that does not contain \(e\). Adding \(e\) to \(T\) creates a cycle \(C\). Since \(e\) crosses \((A, B)\) and \(T\) is a spanning tree, the cycle \(C\) must contain another edge \(f\) that also crosses \((A, B)\). Since \(e\) is the unique lightest crossing edge, \(w(e) < w(f)\). Replacing \(f\) by \(e\) in \(T\) gives a spanning tree of smaller weight — contradicting that \(T\) is an MST. \(\blacksquare\)
For any cycle \(C\) in a connected weighted graph \(G\), if edge \(e\) is the unique heaviest edge in \(C\), then \(e\) does not belong to any MST of \(G\).
Suppose an MST \(T\) contains \(e\). Removing \(e\) from \(T\) splits it into two components, defining a cut \((A, B)\). The cycle \(C\) must contain another edge \(f \neq e\) crossing this cut. Since \(e\) is the unique heaviest in \(C\), \(w(f) < w(e)\). Replacing \(e\) by \(f\) gives a spanning tree of smaller weight — contradiction. \(\blacksquare\)
Given a forest \(F\) that is a subgraph of \(G\), an edge \(e = \{u, v\} \in E \setminus F\) is called \(F\)-heavy if \(w(e)\) is strictly greater than the weight of every edge on the (unique) path from \(u\) to \(v\) in \(F\) (if such a path exists). An edge is \(F\)-light if it is not \(F\)-heavy.
By the cycle property, \(F\)-heavy edges (with respect to the MST) cannot be in any MST.
Borůvka's Algorithm Idea
Each vertex selects its lightest incident edge. All such edges are added to the MST (they are safe by the cut property — each vertex forms its own singleton cut). Then each connected component is contracted into a single super-vertex, and the process repeats. Each round at least halves the number of vertices, so after \(O(\log n)\) rounds the MST is found. One Borůvka step runs in \(O(m)\) time.
Let \(G = (V, E)\) be a connected multigraph and \(F\) a random subgraph obtained by including each edge independently with probability \(p\). Let \(T_F\) be the MST of \(F\). Then the expected number of \(T_F\)-light edges in \(G\) is at most:
\[\mathbb{E}[\text{# of } T_F\text{-light edges}] \leq \frac{|V|}{p}\]This is the key lemma behind the randomised linear-time MST algorithm.
Counting Arguments
Any undirected graph on \(n\) vertices has at most \(\binom{n}{2}\) minimum cuts.
Let \(M\) be the number of distinct min-cuts. Karger's algorithm finds each specific min-cut with probability \(\geq 1/\binom{n}{2}\). Since different min-cuts produce disjoint success events (only one cut can survive as the final 2-vertex partition), and the total probability cannot exceed 1:
\[M \cdot \frac{1}{\binom{n}{2}} \leq 1 \implies M \leq \binom{n}{2}\]\(\blacksquare\)
Total Number of Distinct Cuts
A cut is a partition \((A, B)\) of \(V\) into two non-empty subsets. Since \((A, B)\) and \((B, A)\) are the same cut, the number of distinct cuts is:
\[\frac{2^n - 2}{2} = 2^{n-1} - 1\]We subtract 2 for the empty-set partitions (\(A = \emptyset\) or \(B = \emptyset\)), then divide by 2 for symmetry.
The cycle graph \(C_n\) has \(n\) vertices and \(n\) edges arranged in a single cycle. Every edge has the same weight, and the min-cut has size 2 (remove any two edges to disconnect). The number of min-cuts is exactly:
\[\binom{n}{2}\]To see why: each min-cut corresponds to choosing 2 edges to remove, which is equivalent to choosing 2 "cut points" on the cycle. There are \(\binom{n}{2}\) ways to do this, and each gives a distinct min-cut. This shows the bound \(M \leq \binom{n}{2}\) is tight.
Do not confuse:
- Distinct cuts (partitions into two non-empty subsets): \(2^{n-1} - 1\) total.
- Minimum cuts: at most \(\binom{n}{2}\), achieved by the cycle graph.
For large \(n\), \(\binom{n}{2} = O(n^2)\) is much smaller than \(2^{n-1} - 1\), so min-cuts are a tiny fraction of all cuts.
Math quiz
Chapter math quizzes are in the Quiz Hub. Filter by this chapter and choose Study / Math / All.