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