# 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?

• Since this is intended to be an extension of Mantel's Theorem, do you assume that $G$ is triangle-free? – Andrew Uzzell Apr 23 '13 at 14:58
• Yes, we assume G has no K3. – Musegirl Apr 23 '13 at 15:12

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