Purchase Solution

Graph Theory : Connected Graphs and Disconnected Graphs

Not what you're looking for?

Ask Custom Question

Using the theorems from Graph and Digraphs 4ed by G. Chartrand and L. Lesniak:

1 - (a) Let G a graph of order n such that deg v greater than or equal to (n-1)/2 for every v element of V(G).
Prove that G is connected.
(b) Examine the sharpness of the bound in (a).

2 - Prove the every graph G has a path of length sigma (G) ( minimum degree of G)

3 - Prove that if G is a disconnected graph, then G-bar is connected and, in fact, diam G-bar is less than or equal to 2.

Please can you explain then step by step about definition connected, sharpness, etc

This are the theorems:

Theorem 1.6
Every u-v walk in a graph contains a u-v path.

Theorem 1.7
If A is the adjacency matrix of a graph G with V(G)= {v1,v2,...,v4}, then the (i,j) entry of is the number of different walks of length k in G.
Theorem 1.8
A nontrivial graph is bipartite if and only if it contains no odd cycles.

Theorem 1.9
For every connected graph G ,

Theorem 1.10
Every graph is the center of some graph.

Theorem 1.11
A graph G is the periphery of some connected graph if and only if every vertex of G has eccentricity 1 or no vertex of G has eccentricity.

Attachments
Purchase this Solution
Solution Summary

Connected graphs and disconnected graphs are investigated using the theorems from Graph and Digraphs 4ed by G. Chartrand and L. Lesniak in the attached word document.

Solution Preview

Definition: A graph is connected if there is a path connecting any two distinct vertices of the graph. The sharpness of a bound is the derivative of the bound.

Problem #1
(a) Proof:
We use mathematical induction. If the graph has only one node, then it is already connected. If n =2 , the graph has ...

Purchase this Solution
Free BrainMass Quizzes
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.

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.

Probability Quiz

Some questions on probability

Solving quadratic inequalities

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

View More Free Quizzes
Related BrainMass Solutions

  • Graphs : Connectedness, Vertices and Edges

    28681 Graphs : Connectedness, Vertices and Edges 11. Let G be a graph with n>= 2 vertices. a) Prove that if G has at least (n-1) + 1 edges the G is connected.

  • Cubic Graphs : Connectivity and Edge-connectivity

    To see , we can remove the vertices A and B; OR vertices C and D to make G disconnected. So, . Example 4: A 3-regular graph with One such example can be , complete graph on four vertices.

  • graph theory

    Proof: Let G be a simple connected graph on n >= 3 vertices, and suppose G has a vertex v such that removing v from G results in a disconnected graph (namely, G - {v} -- which is non-trivial since n >= 3).

  • Algebra Problems: Graphs and Functions

    115939 Algebra Problems: Graphs and Functions 1.) An edge of a graph "G" is a bridge of "G" If and only if there exist vertices "U" and "W" such that "e" is on every U - W path of "G". 2.)

  • Graph Theory and Parse Tree

    This solution offers to-the-point answers to some assorted questions on graph theory and parse tree.

  • Hamiltonian Graphs and 2-Connected Graphs

    99736 Hamiltonian Graphs and 2-Connected Graphs Explain this problem with a graph to understand and explain it step by step.

  • elementary theorem in graph theory

    We have only shown that if one is disconnected, then the other is connected. An elementary theorem in graph theory is applied in the solution.

  • Eulerian Graphs

    For such an edge, (n_i+n_j) = odd + even = odd, and so L(G) is not Eulerian. Therefore L(G) can be Eulerian ONLY IF the connected graph G has either all odd or all even vertices. Eulerian graphs are investigated.

  • Spanning Trees and Graphs

    Otherwise it's not connected. Spanning trees and graphs are discussed. The edges of a graph are determined.

View More Related Solutions