# 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, 2013 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. Apr 23, 2013 at 9:09
• @Lord_Farin You are right.
– mez
Apr 23, 2013 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 Apr 23, 2013 at 9:29
• @monalisa I was thinking of this image. Apr 23, 2013 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. Apr 23, 2013 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. Apr 23, 2013 at 9:35
• Oh... got it now. Thanks a lot sir. Apr 23, 2013 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. Apr 23, 2013 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. Jul 16, 2013 at 5:12