Here are my original hand-written notes on this topic.

# The Min-Cut Problem

Throughout, $G=(V,E)$ is an undirected graph that is not necessarily simple. It may have multiple edge between vertices, but it has no self-loops. The graph $G$ has $n$ vertices and $m$ edges.

A *cut* of $G$ is a set of edges whose removal disconnects $G$. A *min-cut* is a cut of minimum cardinality; we denote the size of a min-cut of $G$ as $c(G)$. The *MinCut Problem* asks us to find a *min-cut* of $G$ (or at least to determine its size).

The following lemma gives an easy upper-bound on the size of a min-cut.

**Lemma 1:** $c(G) \le 2m/n$.

*Proof:* The total degree of all vertices in $G$ is $2m$. By the pigeonhole principle, some vertex $v\in V$ has degree $d(v)\le 2m/n$. The edges incident to $v$ form a cut of size $d(v)\le 2m/n$. ∎

**Corollary 1:** Let $C$ be some min-cut of $G$ and select some edge $e$ uniformly at random from among all edges of $G$. Then $\Pr\{e\in C\}\le 2/n$.

*Proof:* By Lemma 1, $|C|\le 2m/n$, so
\[ \Pr\{e\in C\} = \frac{|C|}{m} \le \frac{2m/n}{m} = 2/n \enspace . \]
∎

# Edge Contraction

We define an edge contraction …