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

Laws of set algebra, Laws of Set Algebra From the given Venn diagram w...

Laws of Set Algebra From the given Venn diagram where T is the universal set and A its subset that we can deduce a number of laws as: i. A υ Ø = A ii. A υ T = T

Draw tangent graph y = tan ( x ), Graph y = tan ( x ). Solution In...

Graph y = tan ( x ). Solution In the case of tangent we need to be careful while plugging x's in since tangent doesn't present wherever cosine is zero (remember that tan x

Marketing of herbal products , To help Himalya herbal launch a successful m...

To help Himalya herbal launch a successful marketing campaign in the UK

Algorithm, what does algorithm refer to

what does algorithm refer to

Calculate the monthly payment amount of the loan, Consider a student loan o...

Consider a student loan of $12,500 at a fixed APR of 12% for 25 years, 1. What is the monthly payment amount? 2. What is the total payment over the term of the loan? 3. OF

SHOPPERS`STOP, 3. How are Indian customers visiting Shoppers’ Stop any diff...

3. How are Indian customers visiting Shoppers’ Stop any different from customers of developed western countries? 4. How should Shoppers’ Stop develop its demand forecasts?

Venn diagram, A venn diagram is a pictorial representation of the sam...

A venn diagram is a pictorial representation of the sample space of an experiment. It is usually drawn as a rectangular figure representing the sample space and it cont

Help, I really need help with 30 60 90 right triangles and my last tutor di...

I really need help with 30 60 90 right triangles and my last tutor did not make sense to me so can you please help

Trig functions:, Trig Functions: The intent of this section is introducing...

Trig Functions: The intent of this section is introducing you of some of the more important (from a Calculus view point...) topics from a trig class.  One of the most significant

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