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

Calculate the volume and surface area of a cube, Calculate the volume and s...

Calculate the volume and surface area of a cube: Calculate the volume and surface area of a cube with a = 3".  Be sure to involved units in your answer. Solution: V =

Evaluate the volume of cylinder, If the diameter of a right cylinder is dou...

If the diameter of a right cylinder is doubled and the height is tripled, its volume is a. multiplied by 12. b. multiplied by 2. c. multiplied by 6 d. multiplied by 3.

By the method of completion of squares solve equation, By the method of com...

By the method of completion of squares show that the equation 4x 2 +3x +5 = 0 has no real roots. Ans:    4 x 2 +3 x +5=0 ⇒  x 2 + 3/4 x + 5 = 0 ⇒   x 2 + 3/4 x +

Variation of parameters, In this case we will require deriving a new formul...

In this case we will require deriving a new formula for variation of parameters for systems.  The derivation now will be much simpler than the when we first noticed variation of pa

Areas related to circles in mensuration, AREAS  RELATED TO CIRCLES The...

AREAS  RELATED TO CIRCLES The  mathematical  sciences particularly  exhibit  order,  symmetry,  and limitation;  and  these  are the  greatest  forms  of the beautiful. In t

The invisible effort on learning maths, The Invisible Effort :   Although t...

The Invisible Effort :   Although the development of children is a process, what is noticed and given recognition to is the end-product. We usually speak of children having achieve

Find a formula for its frequency of oscillation, The frequency of oscillati...

The frequency of oscillation of an object suspended on a spring depends on the stiffness k of the spring (called the spring constant) and the mass m of the object. If the spring is

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