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

LINEAR PROGRAMMING, Richland Health has three hospitals in the greater Tamp...

Richland Health has three hospitals in the greater Tampa, Florida area. Demand for patient services varies considerably during the fall and winter months due to the temporary influ

Derivatives of trig functions, Derivatives of Trig Functions In this s...

Derivatives of Trig Functions In this section we will see derivatives of functions other than polynomials or roots of polynomials. We'll begin this process off through taking

Compare and contrast african immigrants, Compare and contrast African immig...

Compare and contrast African immigrants with our immigrant groups? How are they different? What are the implications of these differences for their adjustment to the larger society

Earth geometry, calculate the shortest distance between A and B 40degrees w...

calculate the shortest distance between A and B 40degrees west and 50 degrees east respectively laying along 57 degrees north

Tangent, Tangent, Normal and Binormal Vectors In this part we want to ...

Tangent, Normal and Binormal Vectors In this part we want to look at an application of derivatives for vector functions.  In fact, there are a couple of applications, but they

Interquarticles, (i may have spelled it wrong)but i forgot how to do them.

(i may have spelled it wrong)but i forgot how to do them.

Derivatives of hyperbolic functions , Derivatives of Hyperbolic Functions ...

Derivatives of Hyperbolic Functions : The last set of functions which we're going to be looking at is the hyperbolic functions.  In several physical situations combinations of e

Unit circle, Unit circle: The unit circle is one of the most valuable tool...

Unit circle: The unit circle is one of the most valuable tools to come out in trig.  Unluckily, most people don't study it as well. Below is the unit circle with just the first

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