Randomly Placing Vertices on Two Sides
A cut divides the vertices of a graph into two sides and counts the edges that cross between them. A good cut is one with many crossing edges. Finding a largest cut is an optimization problem, but a simple random procedure already has a useful guarantee: assign every vertex independently and fairly to one of the two sides. Each edge then has probability one half of crossing. Adding these edge-by-edge probabilities shows that the expected cut contains half the edges.
All graphs in this tutorial are finite and simple. For a graph \(G=(V,E)\), a cut is specified by a subset \(S\subseteq V\), with the two sides \(S\) and \(V\setminus S\). Its size is the number of edges with one endpoint in each side. The maximum-cut value, denoted \(\operatorname{OPT}(G)\), is the largest cut size among all choices of \(S\). In particular, \(0\leq \operatorname{OPT}(G)\leq |E|\).
The algorithm makes one fair random choice per vertex, then checks the edges to report the cut size. Its running time is \(O(|V|+|E|)\). If \(V\) is empty, there are no choices or edges and the output size is zero. Isolated vertices can be assigned to either side without affecting the cut.
Why the Expected Cut Has Half the Edges
For each edge \(e\in E\), define an indicator \(X_e\) to be \(1\) if \(e\) crosses the random cut and \(0\) otherwise. The random cut size is \(C=\sum_{e\in E}X_e\). Fix an edge \(uv\). The independent assignments of \(u\) and \(v\) give four equally likely pairs of sides: \((L,L),(L,R),(R,L),(R,R)\). Exactly two pairs cross, so \(\mathbb{E}[X_{uv}]=1/2\).
Proof. If \(E=\varnothing\), then \(C=0\) for every assignment, so \(\mathbb{E}[C]=0=|E|/2\). Otherwise, write \(C=\sum_{e\in E}X_e\). By linearity of expectation for a finite sum, \(\mathbb{E}[C]=\sum_{e\in E}\mathbb{E}[X_e]\). The calculation for a fixed edge gives \(\mathbb{E}[X_e]=1/2\) for every \(e\in E\), and therefore \(\mathbb{E}[C]=\sum_{e\in E}1/2=|E|/2\). This argument does not require the edge indicators to be independent. \(\square\)
The theorem is sometimes described as saying that a random cut contains half the edges. Precisely, it says that the average cut size over the random assignments is half the edge count. A particular assignment can cut more or fewer than half the edges.
The Approximation Guarantee
Proof. Let \(m=|E|\). The first theorem gives \(\mathbb{E}[C]=m/2\). Every cut uses only edges of \(G\), so \(\operatorname{OPT}(G)\leq m\). Dividing this inequality by \(2\) gives \(\operatorname{OPT}(G)/2\leq m/2=\mathbb{E}[C]\), as required. When \(m=0\), both sides are zero, so the conclusion includes the edgeless graph. \(\square\)
This guarantee compares the expected output with the unknown optimum. It does not require finding an optimal cut or knowing its value. It also implies that some cut has size at least \(m/2\): the largest value among the finitely many possible cut sizes is at least their average. Since cut sizes are integers, this means some cut has size at least \(\lceil m/2\rceil\). The randomized algorithm’s expected output is exactly \(m/2\), even when \(m\) is odd and that expectation is not an integer.
Worked Example: A Triangle
Let \(G=(V,E)\), where \(V=\{1,2,3\}\) and \(E=\{12,23,13\}\). The algorithm flips one fair coin for each vertex. Here is one possible run:
| Vertex | Coin result | Assigned side |
|---|---|---|
| 1 | L | L |
| 2 | R | R |
| 3 | L | L |
For this run, edge \(12\) crosses, edge \(23\) crosses, and edge \(13\) does not. The output cut is \(\{12,23\}\), of size \(2\). This is a trace of one outcome, not a statement about every outcome.
To compute the expected size independently, count all \(2^3=8\) equally likely assignments. Two assignments put all three vertices on the same side and cut zero edges. In each of the other six assignments, one vertex is separated from the other two, so exactly two edges cross. Thus the expected size is \((2\cdot 0+6\cdot 2)/8=12/8=3/2\). The edge calculation gives the same answer: there are \(3\) edges, each with crossing probability \(1/2\), so the expectation is \(3\cdot(1/2)=3/2\). A largest cut has size \(2\), since separating one vertex cuts two edges and no cut can cut all three edges of a triangle.
Check: The expected output is \(3/2\), while \(\operatorname{OPT}(G)/2=2/2=1\), so the one-half guarantee holds. This graph also has runs of size zero, as the pitfall discussion explains.
Worked Example: Three Disjoint Edges
Let \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,34,56\}\). In one run, suppose the assignments are as follows:
| Vertex | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Side | L | R | L | R | L | R |
Checking the three edges gives \(12\) crossing, \(34\) crossing, and \(56\) crossing, so this run outputs a cut of size \(3\).
For an independent expectation check, each edge has four equally likely endpoint assignments, of which two cross. The three edge pairs use disjoint vertices, so their cut statuses are independent. For each specified pattern of cut and uncut edges, there are \(2^3=8\) vertex assignments: each edge has two endpoint assignments that realize its specified status. Therefore the numbers of assignments cutting \(0,1,2,3\) edges are respectively \(\binom30 8=8\), \(\binom31 8=24\), \(\binom32 8=24\), and \(\binom33 8=8\), summing to \(64=2^6\). The expected size from this count is \((0\cdot8+1\cdot24+2\cdot24+3\cdot8)/64=96/64=3/2\). The edge-by-edge calculation is \(3\cdot(1/2)=3/2\), as required.
Check: All three edges can cross, so \(\operatorname{OPT}(G)=3\). The expected cut size \(3/2\) equals \(\operatorname{OPT}(G)/2=3/2\), giving equality in the approximation guarantee.
Worked Example: The Complete Graph on Four Vertices
Let \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24,34\}\), so \(G=K_4\). Consider a run that assigns vertices \(1,2\) to \(L\) and vertices \(3,4\) to \(R\):
| Vertex | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Side | L | L | R | R |
Checking the edges, \(12\) and \(34\) do not cross; \(13,14,23,24\) do cross. This run outputs a cut of size \(4\).
To check the expectation by counting assignments, classify them by the number \(k\) of vertices on side \(L\). If \(k=0\) or \(k=4\), there are \(2\) assignments in total and each cuts \(0\) edges. If \(k=1\) or \(k=3\), there are \(\binom41+\binom43=4+4=8\) assignments, each cutting \(1\cdot3=3\) edges. If \(k=2\), there are \(\binom42=6\) assignments, each cutting \(2\cdot2=4\) edges. These counts total \(2+8+6=16=2^4\). The average cut size is \((2\cdot0+8\cdot3+6\cdot4)/16=48/16=3\). Independently, \(K_4\) has \(6\) edges, and \(6\cdot(1/2)=3\) is the expected size by the edge calculation.
Check: A cut with two vertices on each side has size \(4\), and no cut can have more than \(4\) crossing edges because a side of size \(k\) cuts \(k(4-k)\) edges, which is \(0,3,4,3,0\) for \(k=0,1,2,3,4\). Hence \(\operatorname{OPT}(G)=4\), and the expected size \(3\) is at least \(\operatorname{OPT}(G)/2=2\).
What the Guarantee Does Not Say
A common mistake is to treat the expectation as a per-run guarantee. In the triangle example, the two assignments that put all vertices on one side have probability \(2/8=1/4\) and output zero edges. Thus it is false that every run cuts at least half the edges, or at least half the optimum. The theorem controls the average over the random choices.
Another tempting but incorrect calculation is to treat edge-cut events as independent in every graph. In a triangle, each edge has probability \(1/2\) of crossing, but the probability that all three cross is zero: if two vertices lie on opposite sides, a third vertex cannot be on the opposite side from both. Multiplying the three marginal probabilities would incorrectly give \((1/2)^3=1/8\). The expectation proof needs only linearity of expectation, which applies whether or not the edge indicators are independent.
The simple method is useful because its guarantee follows from a short, exact calculation and does not depend on graph structure. Its limitation is equally important: the calculation certifies expected performance, not a fixed lower bound for a particular random outcome. For any graph, the one-half approximation statement is the inequality \(\mathbb{E}[C]\geq\operatorname{OPT}(G)/2\); it should not be rewritten as \(C\geq\operatorname{OPT}(G)/2\) for every run.
Check Your Understanding
Use the edge indicators and the distinction between expectation and individual outcomes when answering.
- For a graph with \(10\) edges, what is the expected cut size under independent fair assignments?
- Explain why a fixed edge crosses with probability \(1/2\), including the role of independent vertex assignments.
- Why does the estimate \(\mathbb{E}[C]=|E|/2\) not require the edge indicators to be independent?
- If a graph has \(9\) edges, what lower bound on the size of some cut follows from the expected-size argument?
- Give a reason the triangle can have an output of zero even though its expected cut size is \(3/2\).