is there a graph with over 5 vertex that is bipartite and self complement

325 Views Asked by At

I want to know if we can draw a graph with at least 5 vertices that is bipartite and self-complement.

1

There are 1 best solutions below

2
On

If $G$ is self-complementary, then $n$ is congruent to 0 or 1 mod 4. Since the only self complementary graph on 5 vertices is $C_{5}$, the next smallest (possible) $n$ is 8. However, if $n \geq 6$ and $G$ is bipartite, then one of the partite sets contains at least three vertices, and thus $G$ has an independent set of size at least 3, so $G^c$ has a clique of size at least 3, and thus a $G^c$ contains a triangle. So no such $G$ exists.