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

Holistic Marketing, Do you believe the holistic marketing concept is the mo...

Do you believe the holistic marketing concept is the most effective way to conduct marketing activities? Why? (Why not?)

How much money did carlie have after she had paid her friend, Carlie receiv...

Carlie received x dollars every hour she spent babysitting. She babysat a total of h hours. She then gave half of the money to a friend who had stopped through to help her. How muc

Rational and irrational numbers, RATIONAL NUMBERS All numbers of the ty...

RATIONAL NUMBERS All numbers of the type p/q where p and q are integer and q ≠0, are known as rational. Thus  it can be noticed that every integer is a rational number

Subtraction of like terms with same signs, Suppose we are required to...

Suppose we are required to find the difference between 3abc and 7abc. We look at two scenarios. The value we would obtain by subtracting a larger quantity from th

Fractions, a boy is six months old his sister was given birth to three mont...

a boy is six months old his sister was given birth to three month after him. if their cousin is 0.33years old, arrange their ages in ascending order

Time & distance., Q4. Assume that the distance that a car runs on one liter...

Q4. Assume that the distance that a car runs on one liter of petrol varies inversely as the square of the speed at which it is driven. It gives a run of 25km per liter at a speed o

Payoff Matrix, A farmer grows apples on her 400-acre farm and must cope wit...

A farmer grows apples on her 400-acre farm and must cope with occasional infestations of worms. If she refrains from using pesticides, she can get a premium for "organically grown"

Determine y' for xy = 1 by implicit differentiation, Determine y′ for xy = ...

Determine y′ for xy = 1 . Solution : There are in fact two solution methods for this problem. Solution 1: It is the simple way of doing the problem.  Just solve for y to

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