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

Find all the real solutions to cubic equation, Find all the real solutions ...

Find all the real solutions to cubic equation x^3 + 4x^2 - 10 =0. Use the cubic equation x^3 + 4x^2 - 10 =0 and perform the following call to the bisection method [0, 1, 30] Use

Generic rectangles and greatest common factors, miaty and yesenia have a gr...

miaty and yesenia have a group of base ten blocks.Misty has six more than yesnia. Yesenia''s blocks repersent 17 together they have 22 blocks,and the total of blocks repersent 85.

Complex number, a ,b,c are complex numbers such that a/1-b=b/1-c=c-1-a=k.fi...

a ,b,c are complex numbers such that a/1-b=b/1-c=c-1-a=k.find the value of k

Range of f(x) =4^x+2^x+1 is, Taking 2^x=m and solving the quadratic for get...

Taking 2^x=m and solving the quadratic for getting D>=0 we get range= [3/4 , infinity )

Impediments in time series analysis, Impediments in time series analysis ...

Impediments in time series analysis Accuracy of data in reflecting a) Drastic changes for illustration in the advent of a major competitor, period of war or unexpected chan

Advanced functions, writ the equation that describes the motion of a point ...

writ the equation that describes the motion of a point on the wheel that has a center of 4m off the ground, has radius of 15 cm, makes a full rotation every 10 seconds and starts a

Particular to general-how mathematical ideas grow, Particular to General : ...

Particular to General :  When I say 'tail', what do you think of? Do you think of the tail of a horse, or of a monkey? Or do you think of the tail of your pet dog? The tail of

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