Self-complementary and bipartite graphs

Question

I'm trying to construct the collection of self-complementary graphs which are also bipartite. For a graph G to be self-complementary, then its complement must be isomorphic to G. If G is bipartite and self-complementary, then I believe that it's complement must also be bipartite. But I'm wondering if the complement is necessarily bipartite on the same subsets of vertices? In other words, if I have a self-complementary bipartite graph G with bipartition (X,Y) where X and Y are subsets of V(G), then is the complement of G also bipartite on (X,Y)? Or can it be bipartite on two different subsets of vertices? In that case, could you still say that the two graphs are isomorphic?

Answer 1

HINT: If both a graph $G$ and its complement are bipartite, then it can have no more than 4 vertices. Indeed, if $G$ is bipartite and has 5 or more vertices, which implies that one side $S$ of $G$ has at least 3 vertices, which implies that the complement of $G$ contains a complete graph on $S$ and thus has a triangle [as $|S| \ge 3$] and is not bipartite.

So now you are left considering graphs on 4 or fewer vertices, which is quite a small enough search space.