Proving a Graph is Connected

Date: 3/19/96 at 0:7:8
From: Jr. John Randazzo
Subject: graph theory

For any graph G that is not connected, how do I prove that its 
complement must be connected?  Can I use induction?  If so, how?

Date: 3/21/96 at 13:30:16
From: Doctor Sebastien
Subject: Re: graph theory

Let G be a disconnected graph with n vertices, where n >= 2.
The complement of G is a graph G' with the same vertex set as G, 
and with an edge e if and only if e is not an edge of G.

Base case:  We know that this is true for n = 2.

   o      o        o---------o
     G                 G'

Assume that this is true for n <= k, where k is any positive integer.
Let this graph be G(k).  The complement G'(k) is connected.
Let's add another vertex - call it X - to G(k).  The graph now has k + 1 
vertices. The vertex X is connected to d vertices, where 0<=d<=k+1.  
It cannot be connected to k vertices, because then then graph would 
be connected. In the complement of the graph, X is connected to k-d 
vertices.  X must be connected to at least one other vertex because 
1<=k-d<=k. Since the complement of G(k) is connected and X is 
connected to at least a vertex in G'(k), then the graph G'(k+1) is also 
connected.  

By the inductive hypothesis, this is true for all n that are positive 
integers.

-Doctor Sebastien,  The Math Forum
  http://mathforum.org/dr.math/   

Date: 3/21/96 at 13:30:16
From: Matthew Daly
Subject: Re: graph theory

There is a more elementary and illuminating proof that is direct.

Let G be a disconnected graph, and let Gc be its complement. (For the
sake of simplicity, we will identify the vertex sets of the two graphs, 
and allow context to show which graph it is referring to.)

Let any two vertices v,v' be given. Either v and v' are in the same 
component of G or they aren't. If they aren't, then they are connected 
in Gc (in fact, they are adjacent). On the other hand, if they are in 
the same component of G, then we may choose a vertex u such that u is 
in a different component from v and v' in G (since G is disconnected). 
Specifically, u is not adjacent to v or v' in G, so it is adjacent to 
both in Gc, so v and v' are in the same component of Gc in this case as 
well.  Since v and v' were arbitrarily chosen, Gc is connected.

The illustrative portion of this proof in contrast to the inductive
proof has the easy corollary that if G is disconnected, then Gc has a 
diameter of either 1 or 2, the former being true only if G has no edges 
at all.

As powerful as the principle of induction is, I think that it is very 
important for students to realize when it should not be used.

-Matthew Daly