Suppose that $G$ is a graph with $2n$ vertices and $n^2$ edges. Let $\epsilon>0$. We say that $G$ is $\mathbf{\epsilon-close}$ to $K_{n,n}$ if $$\frac{|E(G)\triangle E(K_{n,n})|}{\binom{2n}{2}} \leq \epsilon.$$
I would like to show that there exists some partition $V(G)=A_1 \dot\sqcup A_2$ such that the number of edges in $G$ with one end in $A_1$ and one end in $A_2$ is at least $(1-\epsilon)n^2$; that is, $$e(G[A_1, A_2]) \geq (1-\epsilon)n^2.$$
I believe that this can be proven by showing that the expected number of edges between partition sets $A_1$ and $A_2$, where the parts are each of cardinality $n$, is at least $(1-\epsilon)n^2$, given that $G$ is $\epsilon$-close to $K_{n,n}$. If I can prove this, then I know that the partition I want exists.
One can interpret $\frac{|E(G)\triangle E(K_{n,n})|}{\binom{2n}{2}} \leq \epsilon$ $\,$ as saying that the probability that a pair of vertices $\{x,y\}$ is either an edge in $E(G)$ or an edge in $E(K_{n,n})$, but not both, is less than or equal to $\epsilon$ (assuming $\epsilon \leq 1$). Then this means that the probability that a pair of vertices $\{x,y\}$ is an edge in both $E(G)$ and $E(K_{n,n})$ or in neither of these edge sets is at least $1-\epsilon$.
I am not sure where to go from here. It seems that the expectation that I want to compute is conditional, but I do not know how to use the fact that $G$ is $\epsilon$-close to $K_{n,n}$.
Any help is immensely appreciated. Thank you in advance.