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

Curve tracing, Trace the curve (x/a)^3/2+(y/b)^2/3=1

Trace the curve (x/a)^3/2+(y/b)^2/3=1

Determine how many square centimeters, Determine how many square centimeter...

Determine how many square centimeters of paper are needed to make a label on a cylindrical can 45 cm tall with a circular base having diameter of 20 cm. Leave answer in terms of π.

How many inches long is the bedroom, Raul's bedroom is 4 yards long. How ma...

Raul's bedroom is 4 yards long. How many inches long is the bedroom? There are 36 inches within a yard; 4 × 36 = 144 inches. There are 144 inches in 4 yards.

About algebra, how do i compute an algebra number

how do i compute an algebra number

Find out arc length - applications of integrals, Find out the length of y =...

Find out the length of y = ln(sec x ) between 0 x π/4. Solution In this example we'll need to use the first ds as the function is in the form y = f (x). So, let us g

Approximating solutions to equations newtons method, Approximating solution...

Approximating solutions to equations : In this section we will look at a method for approximating solutions to equations. We all know that equations have to be solved on occasion

Shares and dividents., how much money will required to buy 200,rupees 25 sh...

how much money will required to buy 200,rupees 25 shares at premium of rupees 2

Operation research, discuss the sequencing decision problem for n jobs on t...

discuss the sequencing decision problem for n jobs on two and three machines

Algebra 1, how do you factor a trinomial into a binomial ?

how do you factor a trinomial into a binomial ?

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