Bipartite proof Let $G$ be a graph of order $5$ or more. Prove that at most one of $G$ and "$G$ complement" is bipartite. 
I'm lost as to what needs to be done. I know that A nontrivial graph $G$ is bipartite if and only if $G$ contains no odd cycles.
 A: What you need is the fact that, if $G$ is a graph of order $n$, then $\chi(G)\chi(\overline G)\ge n$. To see this observe that, if $V=V(G)=V(\overline G)$, and if $f:V\to[h]$ is a proper coloring of $G$ and $g:V\to[k]$ is a proper coloring of $\overline G$, then $x\mapsto(f(x),g(x))$ is a one-to-one map from $V$ to $[h]\times[k]$.
Now, if $G$ is a graph of order $n$, and if $G$ and $\overline G$ are bipartite graphs, then $n\le\chi(G)\chi(\overline G)\le2\cdot2=4$.
A: Let me give you a hint towards a much, much more elementary solution:
Hint: It is enough to show that if $G$ is bipartite, then $\bar{G}$ (the complement of $G$) is not bipartite.
To that end, suppose that $V(G)=A\cup B$ is a bipartition of $G$.  Then in $E(G)$, there are no edges inside $A$, no edges inside $B$, and there may be some edges between $A$ and $B$.
Based on this, what does $E(\bar{G})$ look like? Since $G$ contains no edges inside $A$ and no edges inside $B$, it must be the case that $\bar{G}$ contains EVERY edge inside $A$ and EVERY edge inside $B$.
So, if $\bar{G}$ WERE bipartite, it couldn't be the case that any two vertices from $A$ or any two vertices from $B$ fell in the same part of the bipartition.
Can you see how to finish it from here, using the assumption that there are at least 5 vertices distributed between $A$ and $B$?
A: What is needed here is Ramsey's theorem.
http://en.wikipedia.org/wiki/Ramsey_theorem
In particular, Ramsey's theorem says that every Graph with 6 or more vertices either has a clique of size three, or its complement has a clique of size three.
A: Assume one of them is bipartite. So, at least one of parts has 3 or more vertices. Let's pick 3 of them and call them u, v, w. As these 3 vertices are in the same part, they have no connection.  Therefore, in the complement graph there are uv, uw and vw edges. Now, u, v, w, u is a cycle of length 3 and it shows that complement graph could not be bipartite. 
