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

Percentage, 7 is what percent of 105?.

7 is what percent of 105?.

Proof for absolute convergence - sequences and series, Proof for Absolute C...

Proof for Absolute Convergence Very first notice that |a n | is either a n or it is - a n depending upon its sign.  The meaning of this is that we can then say, 0 a n +

The expected monetary value method, The expected monetary value method ...

The expected monetary value method The expected pay off as profit associated with a described combination of act and event is acquired by multiplying the pay off for that act a

Speed, Town x and town y were 270km apart. a car started from town x toward...

Town x and town y were 270km apart. a car started from town x towards town y at a uniform speed of 60km/hr, while a motorcycle started from town y to town x at a uniform speed of 9

Determine the velocity and position functions of object, Determine if the a...

Determine if the acceleration of an object is given by a → = i → + 2 j → + 6tk → find out the object's velocity and position functions here given that the initial velocity is v

Prisms, i have to find surface,lateral,and volume

i have to find surface,lateral,and volume

Describe real numbers, Q. Describe Real numbers? Ans. There are a ...

Q. Describe Real numbers? Ans. There are a few different ways to describe real numbers. Without going into any of the very technical definitions used by mathematicians, I'

each player selects one of her two remaining chips , Consider the followin...

Consider the following parlor game to be played between two players. Each player begins with three chips: one red, one white, and one blue. Each chip can be used only once. To beg

Find out if the sets of vectors are parallel or not, Determine or find out ...

Determine or find out if the sets of vectors are parallel or not. (a) a → = (2,-4,1), b = (-6, 12 , -3) (b) a → = (4,10), b = (2,9) Solution (a) These two vectors

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