Slicing graphs

The claim stated in this problem is wrong. The randomized algorithm presented here guarantees that the algorithm does not do worse than the optimal algorithm more than half in expectation . More precisely $\mathbb{E}(\text{Cut}) \geq \frac{1}{2}\text{Max-Cut}$ Where I use the standard term $\text{Cut}$ in place of $\text{Slice}$ . The proof is simple and follows from linearity of expectation. In particular, for any edge $(i,j)\in E$ , the edge is included in the cut iff the vertices $i$ and $j$ are in different partitions, which happens with probability $\frac{1}{2}$ . Thus, $\text{Cut}=\sum_{e\in E} \mathbb{1}(e \in \text{Cut})$ Thus, $\mathbb{E}(\text{Cut})=\sum_{e\in E}\frac{1}{2}=\frac{1}{2}|E|\geq \frac{1}{2}\text{Max-Cut}$ Where the last inequality follows because $|E|$ is a trivial upper bound on $\text{Max-Cut}$ . This proves the result. Note : The Max-Cut problem is a famous hard problem for which no polynomial time algorithm is known which solves it exactly. The best known poly-time approximation algorithm known for Max-Cut has an approximation factor of $\approx 0.878$ and has very deep connection with complexity theory. See the wiki article .