I want to show that I can you can build a two-colorable graph for all n that have n vertices and $\left\lfloor \frac{n^2}{4} \right\rfloor$ edges. After this, I want to show that it is impossible to do the same for any graph that has n vertices and more than $\left\lfloor \frac{n^2}{4} \right\rfloor$ edges.
For n = 0,1,2,3,4, these are quite simple and I see how it could be done. n=2 is $P_2$, n = 3 is $P_3$, and n = 4 is $C_4$. Making these two-colored is not too difficult. I can find a two-colorable graph at n=5, but this was through trial and error. From n = 5 and further, I can not find a definite strategy for making a two colorable graph, as I cannot even find a single way thorugh trial and error for n = 6.
I know that there being $\left\lfloor \frac{n^2}{4} \right\rfloor$ edges is probably the key to this problem, and I would assume knowing why this is the case would help me figure out as to why you cannot do this with any more vertices.
EDIT: Okay, I believe I have found a pattern. If you split the colors as evenly as possible for the vertexes (i.e. if n = 9 then 4 red, 5 blue vertices) then you connect each vertex of one color to every vertex of the other (for the n = 9 example, each of the 4 red vertices can each be connected by an edge to the 5 blue vertices for a total of 4 * 5 edges). This has helped me successfully solve, n = 7,8,9,10. Seeing this pattern, I am having a bit of difficulty mathematically describing the importance of $\left\lfloor \frac{n^2}{4} \right\rfloor$, though I am convinced it works.
Suppose $n=r+s$, so there are $r$ red and $s$ blue vertices. The graph is at most complete bipartite $K_{r,s}$ with $|E|=rs$. We may write this as $|E|=r(n-r)$ and maximize, as a function of real $r$, at $r=n/2$ to get a bound of $|E|\le (n/2)^2$. You can check this bound is tight; it is realized when $n=2r$ (using $K_{r,r}$), and $|E|$ is the nearest integer when $n=2r+1$ (using $K_{r,r+1}$).