Prove that the complement of a disconnected graph G is conne

Prove that the complement of a disconnected graph G is connected. (The complement of a graph G = (V, E) is the graph (V, (V 2)\\E).)

Solution

Solution:

Let G\' denote the complement of G.

Consider any two vertices u, v in G.

If u and v are in different connected components in G, then no edge of G connects them, so there will be an edge {u, v} in G\' .

If u and v are in the same connected component in G, then consider any vertex w in a different connected component (since G is disconnected, there must be at least one other connected component).

By our first argument, the edges {u, w} and {v, w} exist in G\' , so u and v are connected by the path (u, w, v).

Hence any two vertices are connected in G\' , so the whole graph is connected.