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

Geometry, Note on point of tangent

Note on point of tangent

Shares and dividents., how much money will required to buy 200,rupees 25 sh...

how much money will required to buy 200,rupees 25 shares at premium of rupees 2

Pythagorean theorem, when one side of a triangle is 15cm and the bottom of ...

when one side of a triangle is 15cm and the bottom of the triangle is 12cm what would x be rounded to the nearest tenth?

Add or subtract operations for complex numbers, performs the mentioned oper...

performs the mentioned operation and write the answers in standard form. ( -4 + 7 i ) + (5 -10 i ) Solution Actually there isn't much to do here other than add or subt

determine that the relation is symmetric and transitive, 1. Let R and S be...

1. Let R and S be relations on a set A. For each statement, conclude whether it is true or false. In each case, provide a proof or a counterexample, whichever applies. (a) If R

Similar triangles, S IMILAR TRIANGLES : Geometry  is  the  right  ...

S IMILAR TRIANGLES : Geometry  is  the  right  foundation  of all  painting,  I have  decided to  teach its  rudiments  and  principles  to  all  youngsters  eager for  ar

What is the cost of one adult ticket, The cost of a student ticket is $1 mo...

The cost of a student ticket is $1 more than half of an adult ticket. Six adults and four student tickets cost $28. What is the cost of one adult ticket? Let x = the cost 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