Complement of a bipartite graph What constraint must be placed on a bipartite graph G to guarantee that G's complement will also be bipartite?
I see someone saying that it can't be 4 or more in each group, but I don't see why. I thought a constraint would be that the graphs cannot be complete, otherwise the complements would be disconnected.
but, if I take a bipartite graph with 4 vertices on each side, and then connect each vertex from the L to the R horizontally, then if I do the complement, it definitely still seems like a bipartite graph..?
 A: Let $G$ be the bipartite graph and let $V=V_1 \cup V_2$ the splitting of the vertices in the two groups.
Claim Each of $V_1, V_2$ have at most two vertices.
Indeed, if you assume by contradiction that $V_1$ for example has three vertices $u,v,w$ then $u-v-w-u$ is a triangle in the complement, which contradicts the fact that the complement is bipartite.
It follows from here that $G$ has at most $4$ vertices, and it must be a subgraph of $K_{2,2}, K_{1,2}, K_{1,1}$ or $K_1$, covering all possibilities of at most 2 vertices in each group. 
You can now test them one by one.
A: A bipatite graph with a bipartite complement will be very rare.  At the very least, both the graph, and its complement must not have a triangle.  This means the graph cannot have $6$ or more vertices (the Ramsey number $R(3,3)=6$).
There are triangle-free graphs with triangle-free complements on $5$ vertices, but they are isomorphic to a $5$-cycle (which is not bipartite).
So, they must have $4$ or fewer vertices.  For $\leq 3$ vertices, anything other than $K_3$ or $\overline{K_3}$ works.  For $4$ vertices, we can compute the three possibilities:

