Explore BrainMass

Graph Theory : Connected Graphs and Disconnected Graphs

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.


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

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.