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