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

If the area of the parallelogram is 36 m2 what is the height, The height of...

The height of a parallelogram measures 5 meters more than its base. If the area of the parallelogram is 36 m 2 , what is the height in meters? Let x = the measure of the base a

Example for introducing counting, Four-year-old Mariamma was reciting numbe...

Four-year-old Mariamma was reciting number names - some of them in order, and others randomly. The child's aunt, sitting nearby, asked her, "Can you write 'two'?" She said she coul

Ratio, 2qt :6qt::x :48? help me solve x

2qt :6qt::x :48? help me solve x

Vectors, |a.x|=1 where x = i-2j+2k then calculate a

|a.x|=1 where x = i-2j+2k then calculate a

Numerical analysis and computer techniques, write a fortan programme to gen...

write a fortan programme to generate prime number between 1 to 100

Fundamentals of math, When there are 4 dots how many chords are they

When there are 4 dots how many chords are they

Marketing, What are the Input and Output of Marketing

What are the Input and Output of Marketing

One-sided limits, One-sided limits: We do this along with one-sided limits...

One-sided limits: We do this along with one-sided limits.  As the name implies, with one-sided limits we will just looking at one side of the point in question.  Following are the

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