0

If I am given a graph $G = (V, E)$, I understand that a complement of $G'$ is the graph $G$ defined on the same vertex set $V$, however an edge is present in $G'$ provided that it is not in $G$.

How can I prove that if $G$ is not connected, then $G'$ must be connected?

azimut
  • 22,696
choloboy7
  • 35
  • I assume you mean "if $G$ is not connected, then the complement of $G$ is connected"? – icurays1 Mar 25 '13 at 16:35
  • (it is complement btw, not compliment). – Tobias Kildetoft Mar 25 '13 at 16:39
  • Also, recommended notational nicety: use a different symbol, like $H$ or $G^\prime$ for the complement, instead of using $G$ for both. That way you avoid statements like "an edge is present in $G$ provided it is not in $G$", which makes no sense. – icurays1 Mar 25 '13 at 16:40
  • 1
    @TobiasKildetoft but graphs are so nice, don't they deserve a compliment once in a while? ;) – icurays1 Mar 25 '13 at 16:41

1 Answers1

1

Let $G$ be not connected, $A,B$ be two connected components of $G$, $x,y\in V$. If $x\in A$, $y\in B$ then $(x,y)\in G'$. If $x,y\in A$ then choose a vertex $z\in B$. We have $(x,z),(y,z)\in G'$, so $x$ and $y$ are connected in $G'$.

Boris Novikov
  • 17,470