# existence of disconnected, self-complementary graph

Does there exist a disconnected self-complementary graph?

I think no, because if graph is disconnected(connected), then the complementary will be connected(disconnected). Am I proceeding in the right direction. Thanks for your help.

-
The complement of a disconnected graph need not be connected. –  mez Apr 23 '13 at 9:07
@mezhang I think it has to be. Two edges in different conn. components are connected in the complement; two in the same are both connected to all vertices in other conn. comps. Hence the complemented is connected. –  Lord_Farin Apr 23 '13 at 9:09
@Lord_Farin You are right. –  mez Apr 23 '13 at 11:04

You are proceeding in the right direction.

However, if the graph is connected, then its complemented may be connected too; think of $K_5$, split in the pentagon and the five-pointed star.

To show that indeed the complement of a disconnected graph is connected, let $u, v$ be vertices of $G$.

If $u,v$ are in different connected components (CCs), then there is an edge between them in $G^c$. If they are in the same CC, then there is a vertex $w$ in a different CC since $G$ is not connected. Both $u$ and $v$ have an edge to $w$ in $G^c$, hence there is a path from $u$ to $v$ in $G^c$.

-
@Lord_Farin.. isnt complement of $K_5$ is 5 isolated vertices –  monalisa Apr 23 '13 at 9:29
@monalisa I was thinking of this image. –  Lord_Farin Apr 23 '13 at 9:30
Still confused. If we name the vertices as a,b,c,d,e. then every vertex is connected to other four vertices. so in complement adjacent to none. –  monalisa Apr 23 '13 at 9:35
The red graph and the blue graph are each others' complements, but both connected. That's what I was trying to convey. –  Lord_Farin Apr 23 '13 at 9:35
Oh... got it now. Thanks a lot sir. –  monalisa Apr 23 '13 at 9:36

Disconnecton of base graph not implies that complementary graph is connected and vice versa.
Let $G=K_4$ You can decompose it into 2 connected graphs which are self-component(to each other) and also isomorphic.

-
Your example shows at best that the complement of a connected graph needn't be disconnected. It says nothing about disconnected graphs. –  Lord_Farin Apr 23 '13 at 9:16

Does this work?

o----------o

o----------o

thus, G bar =

o o

| |

| |

o o

both graphs are disconnected and both are equal.

-
G bar is connected. It looks like a bow tie. You forgot the diagonal edges. –  Jack Schmidt Jul 16 '13 at 5:12