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

Perimeter and Area, A farmer has a rectangular field of length 100m and bre...

A farmer has a rectangular field of length 100m and breadth 70m. He leaves a path of 1m all along the boundary inside it. He decides to apply a manure to the remaining part of the

Profit, A wholesaler allows a discount of 20% on the list price to a retail...

A wholesaler allows a discount of 20% on the list price to a retailer. The retailer sells at 5% discount on the list price.If a customer paid Rs 114 for an article,what profit is m

Linear programming, I want to send to you a file for my question.How. Could...

I want to send to you a file for my question.How. Could you please send my a link for that.

Poisson mathematical properties, Poisson Mathematical Properties 1. Th...

Poisson Mathematical Properties 1. The expected or mean value = np = λ Whereas; n = Sample Size p = Probability of success 2. The variance = np = ? 3. Standard dev

L''hospital''s rule, L'Hospital's Rule Assume that we have one of the g...

L'Hospital's Rule Assume that we have one of the given cases, where a is any real number, infinity or negative infinity.  In these cases we have, Therefore, L'H

Find out a particular solution to equation, Example: Find out a particular...

Example: Find out a particular solution to y'' - 4y' - 12 y = 3e 5t Solution The point here is to get a particular solution, though the first thing that we're going to

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

Find the are length and sketch the level curves, 1) Find the are length of ...

1) Find the are length of r(t) = ( 1/2t^2, 1/3t^3, 1/3t^3) where t is between 1 and 3 (greater than or equal less than or equal) 2) Sketch the level curves of f(x,y) = x^2-2y^2

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