Suppose we consider the graph $G_n$ with $n$ vertices and $nd$ edges, where we choose every edges $E_1,...,E_{dn}$ uniformly at random from the total set of $n \choose 2$ edges, independently for these $nd$ choices (it is possible to have double edges). Suppose the Max-Cut value of $G_n$ be given by $MC_n$. Then, show that $$P[|MC_n-E(MC_n)| \ge t] \le 2 \exp \left(-\frac{t^2}{2dn} \right)$$
It looks like we can use Chernoff bounds here with $\epsilon=\frac{3t}{2dn}$ but I am not entirely sure if that would work?!
Rather than a Chernoff bound, what you should apply here is Mcdiarmid's inequality [1], also known as the bounded difference inequality[2], [3]. The key point is that replacing one edge in your collection can only change the maxcut value by 1.
[1] https://en.wikipedia.org/wiki/McDiarmid%27s_inequality
[2] https://people.eecs.berkeley.edu/~bartlett/courses/281b-sp06/bdddiff.pdf
[3] web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/09_bounded_difference.pdf