Share
Explore BrainMass

elementary theorem in graph theory

Prove the following theorem:
For any graph G, either G or its complement is connected.

Solution Preview

See the attached file.

Theorem
For any graph G, either G or its complement is connected.

Proof
The proof, as it would appear in a textbook or paper is given below. But each line requires some explanation, which is typically not given as part of the formal proof. Following the proof, a step-by-step version is given. In this, the proof is broken down into several steps, and each step is explained in detail. Please read through the actual proof and try to justify the steps yourself, then look at the explanation:

There are two cases - either G is connected or it is disconnected. If G itself is connected, there is nothing more to prove. Suppose G is disconnected. Then G has at least two components. Let u and v be any two vertices in G. Then, either they are in the same component or they are in different components. If they are in different components, then they are adjacent in the complement. If they are in the same component, then they are both non-adjacent to any vertex of another component, and hence are adjacent to this vertex in the complement. Thus, there is a path between u and v in the complement of G. In both cases, u and v have a path joining ...

Solution Summary

An elementary theorem in graph theory is applied in the solution.

$2.19