Question

Prove that if g is self-complementary then it has 4n or 4n + 1 vertices

Answer 1

Suppose G is disconnected. We want to show that G¯ is connected. So suppose v and w are vertices. If vw is not an edge in G, then it is an edge in G¯, and so we have a path from v to w in G¯. On the other hand, if vw is an edge in G, then this means v and w are in the same component of G. Since G is disconnected, we can find a vertex u in a different component, so that neither uv nor uw are edges of G. Then vuw is a parth from v to w in G¯.

This shows that any two vertices in G¯ have a path (in fact a path of length one or two) between them in G¯, so G¯ is connected.