Q:

Vertex Coloring with Bound on Number of Monochromatic Edges

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}$?

A:

We cannot use Chernoff bounds, because the variables $(X_e)_{e \in E(G)}$ are not, in fact, independent. 
Consider a graph with vertices $1, 2, 3$ and edges $12, 13, 23$. Then $X_{12}, X_{13}, X_{23}$ have a nontrivial relationship: $X_{12} + X_{13} + X_{23}$, the total number of non-monochromatic edges, can be either $0$ (if all three vertices are the same color) or $2$ (otherwise). It cannot be $1$ or $3$. That means that if we know $X_{12}$ and $X_{13}$, then we can deduce $X_{23}$: the variables are not independent.
What they are - and what your argument shows they are - is pairwise independent. One consequence of that is that the sum $X = \sum_{e \in E(G)} X_e$ has the same variance as the binomial distribution. We can see this by computing
\begin{align}
   \mathbb E[X^2] &= \mathbb E\left[\left(\sum_{e \in E(G)} X_e\right)^2\right] \\
 &= \sum_{e \in E(G)} \mathbb E[X_e^2] + \sum_{\substack{e, f \in E(G)  \\ e \ne f}} \mathbb E[X_e X_f] \\
 &= \sum_{e \in E(G)} \frac12 +  \sum_{\substack{e, f \in E(G)  \\ e \ne f}} \frac14 \\
 &= \frac12 m + \frac14 m(m-1) = \frac14 m^2 + \frac14m.
\end{align}
Meanwhile, $\mathbb E[X] = \frac12m$, so $\operatorname{Var}[X] = \mathbb E[X^2] - \mathbb E[X]^2 = \frac14m$. 
(Side note: this calculation only relied on knowing $\mathbb E[X_e X_f] = \mathbb E[X_e] \mathbb E[X_f]$, which is why we get the same result any time that we have pairwise independent random variables.)
For a Chernoff bound, all $m$ of the variables must be mutually independent. But when we only have pairwise independence, we can exploit that using Chebyshev's inequality. This says that
$$
   \Pr[ |X - \mathbb E[X]| \ge t] \le \frac{\operatorname{Var}[X]}{t^2}
$$
and in our case, if we set $t = \sqrt m$, we get $\Pr[ |X - \frac12m| \ge \sqrt m] \le \frac14$.
With probability at least $\frac34$, we have $\frac12 m - \sqrt m \le X \le \frac12m + \sqrt m$, which means in particular that some such outcome must exist.

