Prove that a simple graph is connected, Mathematics

Assignment Help:

Prove that a simple graph is connected if and only if it has a spanning tree.   

Ans: First assume that a simple graph G has a spanning  tree T.  T consists of every node of G.  By the definition of a tree, there is a path among any two nodes of T.  As T is a subgraph of G, there is a path among each pair of nodes in G. Hence G is connected.   

Here now let G is connected. If G is a tree then nothing to prove. If G is not a tree, it must consist of a simple circuit. Let G has n nodes. We can choose (n - 1) arcs from G in such type of a way that they not form a circuit. It results into a subgraph comprising all nodes and only (n - 1) arcs. So by definition this subgraph is a spanning tree.


Related Discussions:- Prove that a simple graph is connected

Number sequence, what is the formula to find a sequence on a string of numb...

what is the formula to find a sequence on a string of numbers?

Algebra, 25 algebraic equations that equal 36

25 algebraic equations that equal 36

What is the measure of its width if its length is 3 inches, The perimeter o...

The perimeter of a rectangle is 21 inches. What is the measure of its width if its length is 3 inches greater than its width? Let x = the width of the rectangle. Let x + 3 = th

What is stem-and-leaf plots, Q. What is Stem-and-Leaf Plots? Ans. ...

Q. What is Stem-and-Leaf Plots? Ans. A stem-and-leaf plot is a table that provides a quick way to arrange a set of data and view its shape, or distribution. Each data val

Tests for relative minimum, Tests for relative minimum For a relative ...

Tests for relative minimum For a relative minimum point there are two tests: i.The first derivative, which is (dy)/(dx)  = f´(x) = 0 ii.The second derivative, which i

Level curves or contour curves - three dimensional space, Level Curves or C...

Level Curves or Contour Curves Another topic that we should look at is that of level curves or also known as contour curves. The level curves of the function z = f (x, y) are t

Hieght and distances, A boy standing in the middle of a field, observes a f...

A boy standing in the middle of a field, observes a flying bird in the north at an angle of elevation fo 30 degree. and after 2 min, he observes the same bird in the south at an an

In the terms of x, The length of Kara's rectangular patio can be expressed ...

The length of Kara's rectangular patio can be expressed as 2x - 1 and the width can be expressed as x + 6. In the terms of x, what is the area of her patio? Since the area of a

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd