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

Correlation coefficient, Correlation coefficient - These are numerical...

Correlation coefficient - These are numerical measures of the correlations existing between the independent and the dependent variables - These are better measures of corre

Project, report on shares and dovidend using newspaer

report on shares and dovidend using newspaer

What is the probability in which she gets heads further flip, Jennifer ?ipp...

Jennifer ?ipped a coin three times and got heads each time. What is the probability in which she gets heads on the further ?ip? The probability of heads does not modify based o

Least cost method in operations research, algorithm and numerical examples ...

algorithm and numerical examples of least cost method

Functions, The figure shows the sketch graphs of the functions

The figure shows the sketch graphs of the functions

What is this distance expressed in standard notation, The distance from the...

The distance from the sun to the earth is approximately 9.3 × 10 7 miles. What is this distance expressed in standard notation? In order to convert this number to standard not

Find out height of the box which will give maximum volume, We contain a pie...

We contain a piece of cardboard i.e. 14 inches by 10 inches & we're going to cut out the corners as illustrates below and fold up the sides to form a box, also illustrated below. F

Example of making connections of a child with maths, After a lot of effort,...

After a lot of effort, 8-year-old Hari worked out 2 x 88 = 176. When asked to say what 2 x 89 was, after a lot of hard work, he produced the answer 178. How would you help him to r

Geometry, find h in the parallelogram

find h in the parallelogram

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