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

Determine the max theoretical information rate, 1 Data is to be transmitted...

1 Data is to be transmitted over Public Switched Telephone Network (PSTN) using 8 levels per signaling elements. If the bandwidth is 3000 Hz, deduce the theoretical maximum transfe

Find x if circle passes through -3, The centre of a circle is (2x - 1, 3x +...

The centre of a circle is (2x - 1, 3x + 1).Find x if the circle passes through (-3,-1) and the length of the diameter is 20 units.

Find the generating function, Find the generating function for the number o...

Find the generating function for the number of r-combinations of {3.a, 5.b, 2.c}          Ans:  Terms sequence is given as r-combinations of {3.a, 5.b, 2.c}. This can be writte

In terms of x what is the volume of the rectangular prism, The dimensions o...

The dimensions of a rectangular prism can be expressed as x + 1, x - 2, and x + 4. In terms of x, what is the volume of the prism? Since the formula for the volume of a rectang

Find the sides of the two squares, The sum of areas of two squares is 468m ...

The sum of areas of two squares is 468m 2  If the difference of their perimeters is 24cm, find the sides of the two squares. Ans:    Let the side of the larger square be x .

Basics of series - sequences and series, Series - The Basics That top...

Series - The Basics That topic is infinite series.  So just define what is an infinite series?  Well, let's start with a sequence {a n } ∞ n=1 (note the n=1 is for convenie

Calculus, The law of cosines can only be applied to acute triangles. Is thi...

The law of cosines can only be applied to acute triangles. Is this true or false?

Characteristics of exponential smoothing, Characteristics of Exponential Sm...

Characteristics of Exponential Smoothing 1. More weight is described to the most recent data. 2. All past data are incorporated not like in moving averages. 3. Les

Basic computation formulas of differentiation, Basic "computation" formulas...

Basic "computation" formulas : Next, let's take a quick look at some basic "computation" formulas that will let us to actually compute some derivatives. Formulas 1)   If f

Word problem, A computer is programmed to scan the digits of the counting n...

A computer is programmed to scan the digits of the counting numbers.For example,if it scans 1 2 3 4 5 6 7 8 9 10 11 12 13 then it has scanned 17 digits all together. If the comput

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