Markov Inequality in graph theory
Let $X$ denote the fraction of remaining edges. We know that $0 \leq X \leq 1$ and $\mathbb{E}[X] = 1/2$. Let us define $Y = 1 - X$, which is the fraction of edges inside $A$ and $B$. This is a non-negative random variable whose expectation is $\mathbb{E}[Y] = 1/2$. According to Markov's inequality,
$$
\Pr[X &lt; 1/4] = \Pr[Y &gt; 3/4] = \Pr[Y &gt; \tfrac{3}{2} \mathbb{E}[Y]] &lt; \frac{2}{3}.
$$
Therefore $\Pr[X \geq 1/4] &gt; 1/3$.

Let us show that the similar inequality $\Pr[X &gt; 1/4] \geq 1/3$ is tight, that is, there exists a random variable satisfying $0 \leq X \leq 1$, $\mathbb{E}[X] = 1/2$, and $\Pr[X &gt; 1/4] = 1/3$. Indeed, take $\Pr[X = 1/4] = 2/3$ and $\Pr[X = 1] = 1/3$, and notice that
$$
\mathbb{E}[X] = \frac{2}{3} \cdot \frac{1}{4} + \frac{1}{3} \cdot 1 = \frac{1}{6} + \frac{1}{3} = \frac{1}{2}.
$$
In a similar way, one can show that $\Pr[X \geq 1/4]$ can be arbitrarily close to $1/3$.