Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
The complement of a disconnected graph need not be connected. –  mez Apr 23 '13 at 9:07
1  
@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

3 Answers 3

up vote 4 down vote accepted

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$.

share|improve this answer
    
@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.

share|improve this answer
1  
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

^above is your G

thus, G bar =

o o

| |

| |

o o

both graphs are disconnected and both are equal.

share|improve this answer
2  
G bar is connected. It looks like a bow tie. You forgot the diagonal edges. –  Jack Schmidt Jul 16 '13 at 5:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.