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

Find the value of x of an arithmetic progressions, Find the value of x if 2...

Find the value of x if 2x + 1, x 2 + x +1, 3 x 2 - 3 x +3 are consecutive terms of an AP. Ans:  a 2 -a 1 =  a 3 -a 2 ⇒   x 2 + x + 1-2 x - 1 = 3x 2 - 3x + 3- x

Explain introduction to non-euclidean geometry, Explain Introduction to Non...

Explain Introduction to Non-Euclidean Geometry? Up to this point, the type of geometry we have been studying is known as Euclidean geometry. It is based on the studies of the a

RATIO, 3 years to 104 weeks,express answer in ratio

3 years to 104 weeks,express answer in ratio

Machines, descuss the seauencing problem for n jobs on two and three machin...

descuss the seauencing problem for n jobs on two and three machines

What is slope of a line, What is Slope of a Line ? A line can have a "...

What is Slope of a Line ? A line can have a "steep" slope or a "gradual" slope. slope = rise/run The "rise" is the distance going up or down. The "run" is the distance goin

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

Percent of a number, Pay $40 for plan offered for $30 for plan what percent...

Pay $40 for plan offered for $30 for plan what percentage of savings

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