4
$\begingroup$

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?

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

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

$\endgroup$
  • $\begingroup$ can anyone complete the proof or give a solution? $\endgroup$ – mathpadawan Dec 6 '18 at 20:29
0
+100
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.