[JosefK]

I believe you mean Max-Cut can be 2 approximated with the trivial random algorithm. Min cut can be solved exactly, and that algorithm would give an expected n^2 approx factor (for min cut).