  The MaxCut problem asks for the size ${\rm mc}(G)$ of a largest cut in a
graph $G$. It is well known that ${\rm mc}(G)\ge m/2$ for any $m$-edge graph
$G$, and the difference ${\rm mc}(G)-m/2$ is called the surplus of $G$. The
study of the surplus of $H$-free graphs was initiated by Erd\H{o}s and Lov\'asz
in the 70s, who in particular asked what happens for triangle-free graphs. This
was famously resolved by Alon, who showed that in the triangle-free case the
surplus is $\Omega(m^{4/5})$, and found constructions matching this bound. We
prove several new results in this area.
  Firstly, we show that for every fixed odd $r\ge 3$, any $C_r$-free graph with
$m$ edges has surplus $\Omega_r\big(m^{\frac{r+1}{r+2}}\big)$. This is tight,
as is shown by a construction of pseudorandom $C_r$-free graphs due to Alon and
Kahale. It improves previous results of several researchers, and complements a
result of Alon, Krivelevich and Sudakov which is the same bound when $r$ is
even.
  Secondly, generalizing the result of Alon, we allow the graph to have
triangles, and show that if the number of triangles is a bit less than in a
random graph with the same density, then the graph has large surplus. For
regular graphs our bounds on the surplus are sharp.
  Thirdly, we prove that an $n$-vertex graph with few copies of $K_r$ and
average degree $d$ has surplus $\Omega_r(d^{r-1}/n^{r-3})$, which is tight when
$d$ is close to $n$ provided that a conjectured dense pseudorandom $K_r$-free
graph exists. This result is used to improve the best known lower bound (as a
function of $m$) on the surplus of $K_r$-free graphs.
  Our proofs combine techniques from semidefinite programming, probabilistic
reasoning, as well as combinatorial and spectral arguments.
