Problem:
Let G be a graph with m edges. Prove that the vertices of G can be colored red and blue so that the number k of non-monochromatic edges satisfies $$\frac{m}{2}-\sqrt{m} \leq k \leq \frac{m}{2}+\sqrt{m}$$
Idea for Proof:
Edit:
Color each vertex red or blue independently with probability $\frac{1}{2}$. Let $A_e$ be the event that e is non-monochromatic and let $X_e$ be its indicator. So $X_e = 1$ if e is non-monochromatic and $X_e = 0$ if e is monochromatic. Let $X = \sum_{e\in E(G)} X_e$, giving the number of non-chromatic edges.
Then, each edge is non-monochromatic with probability $\frac{1}{2}$, so $E[X]=\frac{m}{2}$.
To use Chernoff's inequality we need independence of the random variables.
Claim: for any two edges $e=uv,f=xy \in E(G)$, $X_e$ and $X_f$ are independent random variables.
Case 1: The two edges do not share a vertex. There are $2^4=16$ color assignments for the four vertices u, v, x, and y. There are exactly 4 color assignments where both e and f are non-monochromatic. Then the probability that both e and f are non-monochromatic is $\frac{4}{16}=\frac{1}{4}$.
i.e. $P[X_e=1$ and $X_f=1]=\frac{1}{4} = \frac{1}{2}\cdot \frac{1}{2} = P[X_e=1]\cdot P[X_f=1]$.
Case 2: The two edges share one vertex.
Then there are $2^3=8$ possible color assignment for the three vertices u, v=x, and y (assuming WLOG v=x). There are exactly 2 color assignments where both e and f are non-monochromatic. Then the probability that both e and f are non-monochromatic is $\frac{2}{8}=\frac{1}{4}$.
i.e. $P[X_e=1$ and $X_f=1]=\frac{1}{4} = \frac{1}{2}\cdot \frac{1}{2} = P[X_e=1]\cdot P[X_f=1]$.
Now is it possible to use Chernoff's? Chernoff's: (under certains conditions of the r.v.'s), for any $t\geq0$, $$P[X\geq E[X] + t] \leq e^{\frac{-t^2}{2Var[X]+t/3}}$$ And in this situation, $t=\sqrt{m}$?