# Self-complementary and bipartite graphs

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?

• The vertex sets don't have to be identical. There has to be a one-to-one correspondence that preserves adjacency. Look at the definition of isomorphism again. – saulspatz Sep 29 '19 at 15:39

## 1 Answer

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.