Purchase Solution

Graphs : Connectedness, Vertices and Edges

Not what you're looking for?

Ask Custom Question

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.

Attachments
Purchase this Solution
Solution Summary

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

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

Purchase this Solution
Free BrainMass Quizzes
Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

View More Free Quizzes
Related BrainMass Solutions

  • Trees and Graphs: Does the Graph Exist?

    6988 Trees and Graphs: Does the Graph Exist? Graphs and trees Section 11.5, #16 Either draw a graph with the given specifications or explain why no such graph exists.

  • Graph Isomorphism

    of a pair of non-isomorphic graphs that 4 vertices and 2 edges each is given in the attachment.

  • Undergrad Topology Vertice Proofs

    (v :vertices and e : edges) For the proof we need to introduce a class of special graphs.

  • Eulerian Graphs

    145699 Eulerian Graphs: Odd or Even Vertices Let G be a graph. The line graph L(G) of G is defined to be the graph whose vertices are the edges of G and where two vertices of L(G) are adjacent if the corresponding edges of G are adjacent.

  • Trees and Graphs : Vertices and Edges

    128933 Trees and Graphs : Vertices and Edges 1. True or False. It is possible to obtain a graph in which the number of vertices is 9, each with degree 5. 2. How many edges are there in a tree with 14 vertices? Choose one answer.

  • Directed Graphs and Trees

    YES, if each of the associated vertices have the same degree. -------------------------------------------- Directed graphs and connectedness and isomorphic trees are discussed. The solution is concise.

  • Graph Theory and Parse Tree

    Graphs are classified according to their complexity, the number of edges allowed between any two vertices, and whether or not directions (for example, up or down) are assigned to edges.

  • Outerplanar Graphs

    As H is a planar graph with p+1 vertices and p+q edges, by a known result (Theorem 6.3 on page 156, Graphs and Digraphs, third edition, G. Chartrand and L.

  • Connected Graphs

    Let G be a connected graph and sq(G) be a graph which contains all vertices and edges of G and moreover edges joining every pair of vertices that were in G at distance 2.

View More Related Solutions