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

Systems of equations, Since we are going to be working almost exclusively a...

Since we are going to be working almost exclusively along with systems of equations wherein the number of unknowns equals the number of equations we will confine our review to thes

Probability, The probability that a leap year will have 53 sunday is ? and ...

The probability that a leap year will have 53 sunday is ? and how please explain it ? (a)1/7    (b) 2/7    (c) 5/7    (d)6/7 Sol) A leap year has 366 days, therefore 52 weeks i.e

Word problem, On a canoe trip. a person paddled upstream against the curren...

On a canoe trip. a person paddled upstream against the current ata an average of 2mi/h. the return trip with the current at 3mi/h. Need to find the paddling spped in still water an

What is the greater of two consecutive negative integers, What is the great...

What is the greater of two consecutive negative integers whose product is 132? Let x = the lesser integer and let x + 1 = the greater integer. Because product is a key word for

Free Assignment Test Online, Well, my uncle want me to tutor him in mathema...

Well, my uncle want me to tutor him in mathematics. But, the problem is I don''t know what he already knows about math. It for his Compass Test when he go back to school in the spr

Simple interest, find the simple interest on Rs. 68,000 at 50/3 per annum f...

find the simple interest on Rs. 68,000 at 50/3 per annum for 9 month

Gaussian elimination, Example1 :  Solve the subsequent system of equations....

Example1 :  Solve the subsequent system of equations. -2x 1 + x 2 - x 3 = 4 x 1 + 2x 2 + 3x 3   = 13 3x 1 + x 3 = -1 Solution The initial step is to write d

Venn diagram - set theory and calculus, Venn Diagram - Set theory and calcu...

Venn Diagram - Set theory and calculus A easy way of representing sets and relations among sets is by means of the Venn diagram. Venn diagram includes of a rectangle that pres

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