Graph without cycle length of 3.

Question

Let $ G = (V, E) $ be a graph such that $ | V | = 2n $ for $ n \in \mathbb {N} $. Prove: $$ G \mbox{ has no cycle of length 3} \Rrightarrow | E | \le n ^ 2 $$ Please for advice. I'm trying solve it by 8 hours.

Answer 1

Sketch: We can prove such a graph has no more edges than $K_{\Delta,2n-\Delta}$, and hence $K_{n,n}$, as follows:

• Pick a vertex, $v$ say, of maximum degree $\Delta$. Let $S$ be the set of neighbors of $v$.

• Argue that the vertices of the complete bipartite graph $K_{\Delta,2n-\Delta}$ with vertex bipartition $S \cup (V \setminus S)$ has no fewer edges than the original graph (compare vertex degrees, noting that no vertex in the original graph has degree more than $\Delta$).

Hence the graph has no more edges than $K_{n,n}$ which has $n^2$ edges.

Answer 2

It is similar Mantel's theorem. I think this link will help: http://en.wikipedia.org/wiki/Tur%C3%A1n%27s_theorem