Explore BrainMass

Explore BrainMass

    Graph Theory : Connected Graphs and Disconnected Graphs

    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!

    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.

    © BrainMass Inc. brainmass.com March 4, 2021, 7:20 pm ad1c9bdddf


    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.