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

Obtain the equation of the diagonals, the sides of a quad  taken at random ...

the sides of a quad  taken at random are     x+3y-7=0              x-2y-5=0 3x+2y-7=0               7x-y+17=0  obtain the equation of the diagonals

Find homeomorphisms - complex root, All numbers refer to exercises (and not...

All numbers refer to exercises (and not "computer exercises") in Gallian. §22: 8, 16, 22, 24, 28, 36. In addition: Problem 1: Let a be a complex root of the polynomial x 6 +

Define a cyclic group, Question 1: (a) Show that, for all sets A...

Question 1: (a) Show that, for all sets A, B and C, (i) (A ∩ B) c = A c ∩B c . (ii) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). (iii) A - (B ∪ C) = (A - B) ∩ (A - C).

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

Evaluate the area of the region, Evaluate the area of the region. a...

Evaluate the area of the region. a. 478 units 2 b. 578 units 2 c. 528 units 2 d. 428 units 2   b. Refer to the diagram to evaluate the area of the shaded

Circles, assignment on theorems on circle for class 9

assignment on theorems on circle for class 9

Farmer counting grasshoppers in his fields, Farmer counting grasshoppers in...

Farmer counting grasshoppers in his fields, probably not normally distributed due to growing conditions. After various rows the mean number of grasshoppers is 57 SD 12. What will b

Find the constant rate of 0.01 , Two people are 50 feet separately.  One of...

Two people are 50 feet separately.  One of them begin walking north at rate so that the angle illustrated in the diagram below is changing at constant rate of 0.01 rad/min. At what

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