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 linear in - equation - linear algebra, Explain some Examples of ...

Explain some Examples of linear in - Equation, with solution.

Define degrees and radians, Q. Define Degrees and Radians? Ans. Ju...

Q. Define Degrees and Radians? Ans. Just as your height can be measured in meters or feet and your weight can be measured in pounds or kilograms, angles can be measured in

Algebra 1A, The m&m factory produces 2,500 packs of plain m&ms each day. R...

The m&m factory produces 2,500 packs of plain m&ms each day. Represent the total number of packs of plain m&ms the factory makes each day

Binary to decimal, 01010011 01100101 01101101 01110000 01100101 01110010 00...

01010011 01100101 01101101 01110000 01100101 01110010 00100000 01000110 01101001 00100001

Ineqaulites, how to work out inequalities with negative signs?

how to work out inequalities with negative signs?

Class mid points and class interval or width, Class Mid points This i...

Class Mid points This is very significant values which mark the center of a provided class. They are acquired by adding together the two limits of a provided class and dividi

Parallel lines, Parallel to the line specified by 10 y + 3x= -2 In this...

Parallel to the line specified by 10 y + 3x= -2 In this case the new line is to be parallel to the line given by 10 y ? 3x ? -2 and so it have to have the similar slope as this

Algebra, can I access algebra videos?

can I access algebra videos?

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