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

Complex number, a ,b,c are complex numbers such that a/1-b=b/1-c=c-1-a=k.fi...

a ,b,c are complex numbers such that a/1-b=b/1-c=c-1-a=k.find the value of k

Decision-making under conditions of risk, Decision-making Under Conditions ...

Decision-making Under Conditions of Risk With decision-making under conditions of risk all possible states of nature are known and the decision maker has sufficient knowledge

Sequences and series - calculus, Sequences and Series In this section ...

Sequences and Series In this section we will be taking a look at sequences and infinite series.  In fact, this section will deal approximately exclusively with series.  Though

Relationship between the graph and inverse function, Interesting relationsh...

Interesting relationship between the graph of a function and the graph of its inverse : There is one last topic that we have to address quickly before we leave this section.  Ther

Estimation of population proportions, Estimation of population proportions ...

Estimation of population proportions This form of estimation applies at the times while information cannot be described as a mean or as a measure but only as a percentage or fr

Multiplying mixed numbers, Q. Multiplying Mixed Numbers? Ans. Mult...

Q. Multiplying Mixed Numbers? Ans. Multiplying mixed numbers is a 3-step process: 1. Convert the mixed numbers to improper fractions 2. Multiply the fractions 3.

Find the value a2 + ß2 and (a - ß)2, If  α,β are the zeros of the polynom...

If  α,β are the zeros of the polynomial 2x 2 - 4x + 5 find the value of a) α 2 + β 2   b) (α - β) 2 . Ans : p (x) = 2 x 2 - 4 x + 5           (Ans: a) -1 , b) -6) α + β =

Transpotation, how can you determine trasportation schedule that minimizes ...

how can you determine trasportation schedule that minimizes cost

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