Purchase Solution

elementary theorem in graph theory

Not what you're looking for?

Ask Custom Question

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

Purchase this Solution
Solution Summary

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

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 ...

Purchase this Solution
Free BrainMass Quizzes
Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

View More Free Quizzes
Related BrainMass Solutions

  • Gerhard Gentzen

    Gentzen classifies mathematics into three levels (a classification which goes back to Weyl [1931]) based on how infinity is used: elementary number theory, analysis and general set theory.

  • Matrices : Row Operation Theorems

    In each case, we can find out good the answers through some famous theormes: 1- Theorem-1: Let E be the elementary matrix obtained by performing an elementary row operation on the identity matrix I.

  • Matching problem

    By a theorem from Graph Theory: every k-regular bipartite graph is 1-factorable, in other words, the edge set E(G) can be partioned into disjoint perfect matchings.

  • Graph Theory : Connected Graphs and Disconnected Graphs

    95063 Graph Theory : Connected Graphs and Disconnected Graphs Using the theorems from Graph and Digraphs 4ed by G. Chartrand and L.

  • Chromatic Numbers and Graph Coloring

    The other thing is: you must list in detail all resources which you will have used. If you use references you say like that "It was proved in [1], Theorem 1.2.3, that .... (In here you have to write the theorem).

  • Goat on a Rope Problem

    The following graph shows how the goat can reach and graze half of the field. In this graph, the solid circle is the circular field and the broken circle is the area the goat can reach.

  • Systematic Elimination method to solve the system

    We have the following theorem: Each of the elementary operations (E1), (E2) and (E3), and hence any sequence of them, transform a linear differential system into an equivalent system.

  • Fundamental theorem of calculus

    The second fundamental theorem of calculus holds for a continuous on an open interval and any point in , and states that if is defined by (2) then (3) at each point in .

  • Vertices of a tree

    So, E=n-1 Use a famous formula in the graph theory, The sum of degrees is equal to 2E Hence, we have 11*3+12*2+10*4+(n-11-12-10)*1=2(n-1) Hence, 33+24+40+n-33=2n-2 So, 64

View More Related Solutions