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

Calculate what number of workers should be hired, You are given the followi...

You are given the following information about the amount your company can produce per day given the number of workers it hires. Numbers of Workers Quanti

Fractions, how do you multiply fractions

how do you multiply fractions

Geometry, how do you find the length of a parallel line connecting two exte...

how do you find the length of a parallel line connecting two external circles of different sizes from the outside, given the value of both radius and one parallel line.

What is the square root of 36, What is the square root of 36? To search...

What is the square root of 36? To search the square root (√) you ask yourself, "What number multiplied through itself gives me 36?" 6 .6 = 36; thus, 6 is the square root of 36.

Equilibrium solutions, In the earlier section we modeled a population depen...

In the earlier section we modeled a population depends on the assumption that the growth rate would be a constant. Though, in reality it doesn't make much sense. Obviously a popula

Divide by 1-digit numbers, which experession can be used to check the quoti...

which experession can be used to check the quotient 646 divided by 3

Produce list containing m-vectors delta and lambda, The logarithm of the Po...

The logarithm of the Poisson mixture likelihood (3.10) can be calculated with the following R code: sum(log(outer(x,lambda,dpois) %*% delta)), where delta and lambda are m-ve

Unit rates, which shows the rate 12 inches of rain in 6 hours as a unit rat...

which shows the rate 12 inches of rain in 6 hours as a unit rate

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