For Erdos-Renyi random graphs with average degree d, and uniformly random γdregular graph on n vertices, we prove that with high probability the size of both the Max-Cut and maximum bisection are n(d/4 + P_*\sqrt{d/4} + o(\sqrt{d})) while the size of the minimum bisection is n(d/4 - P_*\sqrt{d/4} + o(\sqrt{d})) Our derivation relates the free energy of the anti-ferromagnetic Ising model...