Prove that every triangle-free graph on n vertices has chromatic number at most 2√n. How do I start the proof? Do I start by creating any triangle free graph or is there a theorem that I need to use? 
 A: The easiest way to do this is with the probabilistic method.  I'll give you a quick outline:

*

*Prove that every triangle-free graph has at most $\lfloor n^2 /4\rfloor$ edges.

*Randomly color each vertex of your graph, independently and uniformly with $\lfloor 2 \sqrt{n} \rfloor$ colors.

*Calculate the expected number of edges that are incident on vertices of the same color.

*Conclude that there exists a proper coloring with $\lfloor 2 \sqrt{n} \rfloor$ colors, implying that the chromatic number is $\leq 2 \sqrt{n}.$
EDIT (~4 years later): I don't think this sketch works, I honestly have no idea how I imagined it did.  Here's a more legitimate one.
Let's prove it by induction:

*

*Show that since G is triangle free it has an independent set of size $\sqrt{n}$ [Hint: if there is a vertex of degree $\sqrt{n}$ its neighbors form an independent set; if all vertices have degree $< \sqrt{n}$ how big is the biggest independent set?].


*Color your biggest independent set.  You now have a graph on $n-\sqrt{n}$ vertices that you want to color with $2\sqrt{n} - 1$ colors, which follows by induction.
A: Let $G=(V,E)$ be a triangle-free graph on $n$ vertices, and let $k=\lfloor\sqrt n\rfloor$. I will show that $\chi(G)\le2k$. I assume that $n\gt8$ (and so $k\ge2)$ the smaller cases being trivial.
Let $\mathcal S=\{S_1,\dots,S_m\}$ be a maximal collection of pairwise disjoint independent sets of cardinality $k$; then $mk\le n\lt(k+1)^2$, so $m\le k+2$.
Let $S=S_1\cup\cdots\cup S_m$ and let $T=V\setminus S$, so that $\chi(G)\le\chi(G[S])+\chi(G[T])$.
Because $\mathcal S$ is maximal, $T$ contains no independent set of cardinality $k$. Since $G$ is triangle-free, this means that $G[T]$ has maximum degree less than $k$. It follows that $\chi(G)\le\chi(G[S])+\chi(G[T])\le m+k$.
Case 1. If $m\le k$ then $\chi(G)\le m+k\le2k$.
Case 2. If $m=k+1$ then $|T|=n-|S|\le(k^2+2k)-(k+1)k=k$ and $\chi(G)\le\chi(G([S])+\chi(G[T])\le(k+1)+(k-1)=2k$, unless $G([T])$ is a complete graph of order $k$. But in that case we have $k\le2$ (since $G$ is triangle-free) and $n\le8$, contrary to our assumption that $n\gt8$.
Case 3. If $m=k+2$ then $|S|=k^2+2k=n$ and $S=V$, so $\chi(G)=m=k+2\le2k$.
