Explore BrainMass

Graphs : Connectedness, Vertices and Edges

This content was STOLEN 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 October 24, 2018, 6:01 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.

See Also This Related BrainMass Solution

Graphs and Vector Calculus

Please help answer the following question. Provide step by step calculations along with detailed explanations to explain how each step works.

If all edges of Kn (a complete graph) have been coloured red and blue, how do we show that either the red graph or the blue graph is connected?

View Full Posting Details