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

Do all our activities involve mathematics?, Do All Our Activities Involve M...

Do All Our Activities Involve Mathematics? :  The answer to this is 'yes' and 'no'. For those who look for mathematics and know where to look for it, it is 'yes'. For those who do

Magnitude, find the magnitude of the following vectors:5i+7j

find the magnitude of the following vectors:5i+7j

Pair of linear equations in two variables, a lending library has a fixed ch...

a lending library has a fixed charge for the first three days and an additional charge for each day thereafter. sam paid Rs 27 for a bookkept for 7 days while jaan paid Rs 21 for t

Minimum value of the function, How the property AM>or = GM used to get min...

How the property AM>or = GM used to get minimum value of the function......e,g for what condition of a and b does minimum value of a tan^2 x + b cot^2 x equals maximum value of a

Sqares, Recently I had an insight regarding the difference between squares ...

Recently I had an insight regarding the difference between squares of sequential whole numbers and the sum of those two whole numbers. I quickly realized the following: x + (x+1)

Determine the domain of the function, Determine or find out the domain of t...

Determine or find out the domain of the subsequent function. r → (t) = {cos t, ln (4- t) , √(t+1)} Solution The first component is described for all t's. The second com

Determine the eigenvalues and eigenvectors of the matrix, Determine the eig...

Determine the eigenvalues and eigenvectors of the subsequent matrix. Solution : The first thing that we require to do is determine the eigen-values. It means we require

Analytical geometry, convert the equation 4x^2+4y^2-4x-12y+1=0 to standard ...

convert the equation 4x^2+4y^2-4x-12y+1=0 to standard form and determine the center and radius of the circle. sketch the graph.

Think smarter, compare: 643,251; 633,512; and 633,893. the answer is 633,51...

compare: 643,251; 633,512; and 633,893. the answer is 633,512. what is the question?

Evaluate the area of the shaded region, Evaluate the area of the shaded reg...

Evaluate the area of the shaded region in terms of π. a. 8 - 4π b. 16 - 4π c. 16 - 2π d. 2π- 16 b. The area of the shaded region is same to the area of the squa

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