Extension of Mantel's theorem How would one extend the proof of Mantel's Theorem to show that if $G$ is a graph with $n$ vertices and $\lfloor n^2/4\rfloor - t$ edges then $G$ contains a bipartite subgraph with at least $\lfloor n^2/4\rfloor - 2t$ edges?
 A: For every vertex $x$, we can let $A_x$ be all the neighbors of $x$ and $B_x$ be all the non-neighbors of $x$. Because $G$ is triangle-free, $A_x$ is an independent set, so if we delete all the edges in $E(B_x)$, we get a bipartite graph with bipartition $(A_x, B_x \cup \{x\})$.
It remains to choose a vertex $x$ for which $|E(B_x)|$ is small. What follows is just an elaboration on the one-line proof of Lemma 2.1 in "How to make a graph bipartite" by Erdős, Faudree, Pach, and Spencer.
We have
$$
    \sum_{x \in V(G)} |E(B_x)| = \sum_{vw \in E(G)} (n - \deg(v) - \deg(w)).
$$
The second sum counts for every edge $vw$ all the vertices not adjacent to $v$ or $w$: here we are using the fact that $G$ is triangle-free and therefore no vertex is adjacent to both. The vertices not adjacent to $v$ or $w$ are precisely the vertices $x$ for which $vw \in E(B_x)$. Therefore the two sums count pairs $(x, vw)$ where $vw \in E(B_x)$ in two different ways, so they're equal.
Expanding out the second sum, we get
$$
    \sum_{x \in V(G)} |E(B_x)| = \sum_{vw \in E(G)} (n - \deg(v) - \deg(w)) = n|E(G)| - \sum_{v \in V(G)} \deg(v)^2
$$
because $\deg(v)$ is subtracted once for each of the $\deg(v)$ edges out of $v$. By the convexity of $x \mapsto x^2$, or by Cauchy-Schwarz, the sum of squares is minimized when $\deg(v) = \frac{2|E(G)|}{n}$ for all $v$, and therefore
$$
    \sum_{x \in V(G)} |E(B_x)| = n|E(G)| - \sum_{v \in V(G)} \deg(v)^2 \le n|E(G)| - n \cdot \frac{4|E(G)|^2}{n^2}.
$$
If we substitute $|E(G)| = \frac{n^2}{4} - t$ into this inequality and simplify, the right-hand side becomes $n(\frac{n^2}{4}-t) - \frac{4}{n}(\frac{n^2}{4}-t)^2 = \frac{n^3}{4} - nt - \frac{n^3}{4} + 2nt - \frac{4t^2}{n} = nt - \frac{4t^2}{n}$, so we get
$$
    \sum_{x \in V(G)} |E(B_x)| \le tn - \frac{4t^2}{n} \iff \frac1n \sum_{x \in V(G)} |E(B_x)| \le t - \frac{4t^2}{n^2}
$$
and therefore there is some choice of $x$ for which $|E(B_x)| \le t - \frac{4t^2}{n^2}$. By deleting the edges of $B_x$ from $G$, we get a bipartite subgraph containing all but at most $ t - \frac{4t^2}{n^2}$ edges of $G$: therefore we have at least
$$
   \frac{n^2}{4} - t - \left(t - \frac{4t^2}{n^2}\right) = \frac{n^2}{4} - 2t + \frac{4t^2}{n^2} \ge \frac{n^2}{4} - 2t
$$
edges in the bipartite subgraph.
A: Here is an attempt: Consider a bipartition $(A,B)$ of the vertices of the graph $G$ such that the number of edges between the two bipartition is maximized. So then we can see that this bipartite subgraph $H$ has the property: $v \in V(H)$ then $deg(v)_{H} \geq \frac{deg(v)_G}{2}$. So $2|E(H)|=\sum_{v\in V(H)}deg(v) \geq \sum_{v\in V(G)}\frac{deg(v)}{2}=\frac{2|E(G)|}{2}=\lfloor \frac{n^2}{4} \rfloor -t$. so then $|E(H)|\geq \frac{\lfloor \frac{n^2}{4} \rfloor -t}{2}$.
