Complement of a bipartite graph

Question

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..?

Answer 1

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.

Answer 2

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: