8
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ The complement of a disconnected graph need not be connected. $\endgroup$
    – mez
    Apr 23, 2013 at 9:07
  • 1
    $\begingroup$ @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. $\endgroup$
    – Lord_Farin
    Apr 23, 2013 at 9:09
  • $\begingroup$ @Lord_Farin You are right. $\endgroup$
    – mez
    Apr 23, 2013 at 11:04

3 Answers 3

7
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ @Lord_Farin.. isnt complement of $K_5$ is 5 isolated vertices $\endgroup$
    – monalisa
    Apr 23, 2013 at 9:29
  • $\begingroup$ @monalisa I was thinking of this image. $\endgroup$
    – Lord_Farin
    Apr 23, 2013 at 9:30
  • $\begingroup$ 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. $\endgroup$
    – monalisa
    Apr 23, 2013 at 9:35
  • 2
    $\begingroup$ The red graph and the blue graph are each others' complements, but both connected. That's what I was trying to convey. $\endgroup$
    – Lord_Farin
    Apr 23, 2013 at 9:35
  • $\begingroup$ Oh... got it now. Thanks a lot sir. $\endgroup$
    – monalisa
    Apr 23, 2013 at 9:36
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Your example shows at best that the complement of a connected graph needn't be disconnected. It says nothing about disconnected graphs. $\endgroup$
    – Lord_Farin
    Apr 23, 2013 at 9:16
0
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ G bar is connected. It looks like a bow tie. You forgot the diagonal edges. $\endgroup$ Jul 16, 2013 at 5:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .