Krdytkyu

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/4rfloor - t$ edges then $G$ contains a bipartite subgraph with at least $lfloor n^2/4rfloor - 2t$ edges?

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_{vin V(H)}deg(v) geq sum_{vin 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}$.

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 left-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.