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

What is negative exponents explain, What is Negative Exponents explain? ...

What is Negative Exponents explain? Here's a problem which results in a negative exponent: 3 4 /3 7 = 3 (4-7) = 3 -3 A negative exponent means the same thing as making

Integration, Integration We have, so far, seen that differential ...

Integration We have, so far, seen that differential calculus measures the rate of change of functions. Differentiation is the process of finding the derivative

Probability, Ratio of successes in 5 independent trials to the probability ...

Ratio of successes in 5 independent trials to the probability of successes in two independent trials is 1/4. What is the probability of 4 successes in 6 independent trials?

Math problem, integral from 0 to pi of dx/(a+b*cos(x)

integral from 0 to pi of dx/(a+b*cos(x)

Acid solution, A 90% acid solution is mixed with a 97% acid solution to obt...

A 90% acid solution is mixed with a 97% acid solution to obtain 21 litres of a 95% solution. Findout the quantity of every solutions to get the resultant mixture.

How many feet is the new length if the new area is 141, A rectangular garde...

A rectangular garden has a width of 20 feet and a length of 24 feet. If each side of the garden is increased through the similar amount, how many feet is the new length if the new

Prove that the length of the altitude on the hypotenuse, If A be the area o...

If A be the area of a right triangle and b one of the sides containing the right angle, prove that the length of the altitude on the hypotenuse is 2  Ab /√ b 4 +4A 2 . An

Determine the length of the rectangle, The height of a rectangle is 20 cm. ...

The height of a rectangle is 20 cm. The diagonal is 8 cm more than the length. Determine the length of the rectangle. a. 20 b. 23 c. 22 d. 21 d. To determine the len

Solve out the linear equations, Solve out each of the following equations. ...

Solve out each of the following equations.                3( x + 5)= 2 ( -6 - x ) - 2x Solution In the given problems we will explained in detail the first problem and t

Help, dividing decimals

dividing decimals

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