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

Example of division , Example of division: Divide 738 by 83. Soluti...

Example of division: Divide 738 by 83. Solution: Example: Divide 6409 by 28. Solution: Division could be verified through multiplying

Example of least common denominator, Example of Least Common Denominator: ...

Example of Least Common Denominator: Example: Add 1/7 +2 /3 + 11/12 + 4/6 Solution: Step 1:             Find out primes of each denominator. 7 = 7 (already is

Calculate the probability, Coal is carried from a rrrine in West Virginia t...

Coal is carried from a rrrine in West Virginia to a power plant in New York in hopper cars on a long train. The automatic hopper car loader is set to put 36 tons of coal in each ca

Find the value of the first instalment, A man arranges to pay a debt of Rs....

A man arranges to pay a debt of Rs.3600 in 40 monthly instalments which are in a AP. When 30 instalments are paid he dies leaving one third of the debt unpaid. Find the value of th

volumes for solid of revolution, Volumes for Solid of Revolution Befo...

Volumes for Solid of Revolution Before deriving the formula for it we must probably first describe just what a solid of revolution is. To find a solid of revolution we start o

Discrete mathematics for computing, Everything stored on a computer can be ...

Everything stored on a computer can be represented as a string of bits. However, different types of data (for example, characters and numbers) may be represented by the same strin

Kara brought $23 with her when she went shopping, Kara brought $23 with her...

Kara brought $23 with her when she went shopping. She spent $3.27 for lunch and $14.98 on a shirt. How much money does she have left? The two items that Kara bought must be sub

Why learn mathematics, Here we have considered the following points. 1. ...

Here we have considered the following points. 1. Mathematics is omnipresent, powerful and beautiful. 2. Mathematics is useful in all spheres of life. 3. Mathematics can al

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