how can I proof that a graph with 2n vertices is bipartite

Question

If I have a graph without triangels 2n vertices and n^2 edges is it a bipartite graph? I couldn't find a counter example.

Answer 1

A consequence of Turan's theorem: If a graph, $G$, is traingle free, then $|E(G)| \le n^2/4$ where $n$ is the order of the graph. Translating this to our specific case, we have that $E(G)=n^2 \le \frac{(2n)^2}{4}=n^2$. Thus, our graph has the maximum number of edges to be triangle free, and so it is the Turan graph $T(2n,2)=K_{n,n}.$ Therefore, it is indeed bipartite.

Answer 2

Hint: bipartiteness is equivalent to having no odd cycles.