Associated Topics || Dr. Math Home || Search Dr. Math

### 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
```
Associated Topics:
College Discrete Math

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search