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
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.