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

Logarithms, We know that 2 4 = 16 and also that 2 is referred to as ...

We know that 2 4 = 16 and also that 2 is referred to as the base, 4 as the index or power or the exponent. The same if expressed in terms of logarithms would be log 2

Calculus, I need an explanation of "the integral, from b to a, of the deriv...

I need an explanation of "the integral, from b to a, of the derivative of f (x). and, the integral from a to b. of the derivative of f(t) dt.

Midpoint rule - approximating definite integrals, Midpoint Rule - Approxima...

Midpoint Rule - Approximating Definite Integrals This is the rule which should be somewhat well-known to you. We will divide the interval [a,b] into n subintervals of equal wid

Regression, Regression line drawn as y=c+1075x, when x was 2, and y was 239...

Regression line drawn as y=c+1075x, when x was 2, and y was 239, given that y intercept was 11. Caculate the residual

Find the area of triangle, Find the area of TRIANGLE ? To find the area...

Find the area of TRIANGLE ? To find the area of a triangle, multiply the base (b) by the height (h), and divide the resulting number in half. In other words, area is. It is

Draw grouped frequency tables, Q. Draw Grouped Frequency Tables? Ans. ...

Q. Draw Grouped Frequency Tables? Ans. Grouped frequency tables are often used when there are many different values. In these tables, the values are grouped into classes

Proof of root test - sequences and series, Proof of Root Test  Firstly...

Proof of Root Test  Firstly note that we can suppose without loss of generality that the series will initiate at n = 1 as we've done for all our series test proofs.  As well n

Gravity, There is a list of the forces which will act on the object. Gr...

There is a list of the forces which will act on the object. Gravity, F g The force because of gravity will always act on the object of course. Such force is F g   = mg

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