Let $G=(V,E)$ be a graph. There exists a cut of $G$ with value at least $|E|/2.$ ###### Proof by probabilistic method (1): Consider the random experiment where we assign each element of $V$ to one of two sets independently with probability $\frac{1}{2}$ each. Then the sample space $\Omega$ is the set of all cuts of $G.$ *(💭Note: one of the sets can be empty which is doesn't give a partition. However, we can just define $\Omega$ to be the set of all cuts and $\mathbb{P}$ to be a uniform probability measure on $\Omega.$)* Let $m:=|E|.$ Let $e_{1},e_{2},\dots,e_{m}$ be an enumeration of the elements of $E.$ For $i=1,2,\dots,m,$ define $X_{i}:\Omega\to \{ 0,1 \}$ by $X_{i}(\omega)=\begin{cases} 1 & e_{i} \text{ in cut } \omega \\ 0 & \text{otherwise} \end{cases}$Then for all cuts $\omega\in \Omega,$ $X(\omega)=\sum_{i=1}^{m} X_{i}(\omega)$ is the value of the cut. Now by linearity of expectation $\mathbb{E}[X]=\sum_{i=1}^{m}\mathbb{E}[X_{i}] = \sum_{i=1}^{m} \mathbb{P}(X_{i}=1) = \frac{m}{2}$noting that $\mathbb{P}(X_{i}=1)$ is the probability that the endpoints of $e_{i}$ doesn't lie in the same partition which equals $\frac{1}{4}+\frac{1}{4}=\frac{1}{2}.$ Finally, we conclude by [[Probabilistic Method|expectation method]] that there exists cut of $G$ with value at least $m/2=|E|/2.$ - [x] Complete ✅ 2024-06-17 **Comment**: The [[Randomized Max-Cut Approximation Algorithm]] applies the random process applied above until we gain a cut of size at least $|E|/2.$ ###### Proof by induction: Remove an arbitrary vertex, $v,$ from $G.$ Let $k=\deg(v).$ Then by the inductive hypothesis, there exists a cut of $G-\{ v \}$ of value at least $(|E|-k)/2.$ Now add $v$ into the subset that adds more edges to the cut. Thus we add at least $k/2$ edges to the cut which gives a cut of $G$ of value at least $|E|/2.$ **Comment**: the crux of the inductive step is placing a vertex in the partition that adds the most edges to the cut which is the same idea used in the [[Deterministic Max-Cut Approximation Algorithm]]. # Applications **Generalisations**: [[Lower Bound for Maximum k-Cut]] asserts that .... # References 1. [[Week 9 Max Cut.pdf]].