Explore BrainMass

Explore BrainMass

    elementary theorem in graph theory

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

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

    © BrainMass Inc. brainmass.com March 4, 2021, 10:44 pm ad1c9bdddf

    Solution Preview

    See the attached file.

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

    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.