Explore BrainMass

Explore BrainMass

    Graphs : Connectedness, Vertices and Edges

    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!

    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.
    ( 2 )

    b) Show that the result in (a) is best possible; that is, for each n>= 2, prove there is a graph with (n- 1)
    ( 2 )
    edges that is not connected.

    © BrainMass Inc. brainmass.com December 24, 2021, 5:06 pm ad1c9bdddf


    Solution Preview

    Please see the attached file.

    (a) Prove by contradiction:
    We know the number of edges in a complete graph with n nodes is (because in a complete graph, every node is connected to other n-1 nodes, therefore the degree of every node is (n-1), and the total degree of ...

    Solution Summary

    Connectedness, Vertices and Edges are investigated. The solution is detiled and well presented.