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

Limit comparison test - sequences and series, Limit Comparison Test Ass...

Limit Comparison Test Assume that we have two series ∑a n and ∑b n with a n , b n   ≥ 0 for all n. Determine, If c is positive (i.e. c > 0 ) and is finite (i.e. c

Word problem time vs desent, altitude 35000 @ 9:30 9;42 alt 17500 increase...

altitude 35000 @ 9:30 9;42 alt 17500 increase speed by factor of 3 level out at 2500= how much time will it take

Consumer behaviour, what is consumer behaviour according to accounting

what is consumer behaviour according to accounting

Metric space, Assume that (X, d) is a metric space and let (x1, : : : , x n...

Assume that (X, d) is a metric space and let (x1, : : : , x n ) be a nite set of pointsof X. Elustrate , using only the de nition of open, that the set X\(x1, : : : , x n ) obtain

If the squared difference of the zeros find the value of p, If the squared ...

If the squared difference of the zeros of the quadratic polynomial x 2 + p x + 45 is equal to 144 , find the value of p.

Area problem, Area Problem Now It is time to start second kind of inte...

Area Problem Now It is time to start second kind of integral: Definite Integrals.  The area problem is to definite integrals what tangent & rate of change problems are to d

Write the value of sin10+sin20+sin30+....+sin360., sin10+sin20+sin30+....+s...

sin10+sin20+sin30+....+sin360=0 sin10+sin20+sin30+sin40+...sin180+sin(360-170)+......+sin(360-40)+sin(360-30)+sin(360-20)+sin360-10)+sin360 sin360-x=-sinx hence all terms cancel

Value delivery, What do you mean by value delivery

What do you mean by value delivery

Math, is this free for LIFE that means forever never ever going to pay

is this free for LIFE that means forever never ever going to pay

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