Prove that an even order ($n=2k$) graph without cycle of order 3, has a size $m \le k^2$

Question

Let G be a graph of order n and size m that does not have any cycle of length 3. Prove that if $n=2k$, then $m \le k^2$.

How should I go about proving this? I can use either induction, contradiction, or contrapositive. When I asked my teacher for help, she said that since graph G cannot have any cycle of length three, we will assume that graph G is bipartite, because 3 is an odd cycle and a bipartite graph cannot have an odd cycle. But this doesn't make sense to me because can't we have a cycle of 5? or 7? Please help.

Answer 1

I am not aware of this general theorem that Stefan posts about. Here's a combinatorial approach:
For now, assume $3|n$. We shall handle the 2 special cases later. Divide the vertices into sets of 3. Any set of 3 vertices has atmost 2 edges in it.
Consider any two such sets. There can be atmost 5 edges that can pass between these two sets, if both of them contain 2 edges. Hence, the total number of edges is bounded by: $$m \leq \frac{2*n}{3}+5* \binom{\frac{n}{3}}{2}$$ From here you can get that this is bounded above by $\frac{n^2}{4}$. I hope you can argue out the rest of the cases, which should have a similar reasoning.

Answer 2

By Mantel's Theorem we have that any triangle-free graph has at most $\left[ \frac{n^2}{4} \right] = k^2$ edges. From here we conclude that $m \le k^2$

To prove the Mantel's Theorem we consider the sums of degrees $d(w) + d(v)$, where $wv \in E(G)$. If there's no triangle, then we have that $d(w) + d(v) \le n$, so $$\sum d(v)^2 = \sum_{vw \in E(G)} d(v) + d(w) \le mn$$

On the other side by Handshake's Lemma and Cauchy-Schwartz Inequality we have:

$$\sum d(v)^2 \ge \frac 1n \left(\sum d(v)\right)^2 = \frac{4m^2}{n}$$

From this two inequalies we determine that $mn \ge \frac{4m^2}{n} \implies m \le \frac{n^2}{4}$