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

Introduction to computers, What is a Computer? A computer is ...

What is a Computer? A computer is an electronic device which senses or accepts input data, performs operations or computations on the data in a pre-arranged sequence

Geography, How do you find the maxima or minima on a parabolic graph?

How do you find the maxima or minima on a parabolic graph?

Graph and algebraic methods , To answer each question, use the function t(r...

To answer each question, use the function t(r) = d , where t is the time in hours, d is the distance in miles, and r is the rate in miles per hour. a. Sydney drives 10 mi at a c

Nonhomogeneous differential equations, Let's here start thinking regarding ...

Let's here start thinking regarding that how to solve nonhomogeneous differential equations.  A second order, linear non-homogeneous differential equation is as y′′ + p (t) y′ +

how much error, For a population with a mean of μ=70 and a standard deviat...

For a population with a mean of μ=70 and a standard deviation of o=20, how much error, on average, would you expect between the sample mean (M) and the population mean for each of

Fact - undetermined coefficients, Here, let's take a look at sums of the fu...

Here, let's take a look at sums of the fundamental components and/or products of the fundamental components. To do this we'll require the following fact. Fact- Undetermined Co

What is the average number of miles lori ran, Lori ran (5)1/2 miles Monday,...

Lori ran (5)1/2 miles Monday, (6)1/4 miles Tuesday (4)1/2 miles Wednesday and (2)3/4 mile on Thursday what is the average number of miles lori ran ? To find the average, add

Circle, a wheel revolves 360 deegre revolution in one minute .Find how many...

a wheel revolves 360 deegre revolution in one minute .Find how many radians will the wheel subtend in one second

Round this number to the closest thousandth, It takes the moon an average o...

It takes the moon an average of 27.32167 days to circle the earth. Round this number to the closest thousandth. The thousandths place is the third digit to the right of the dec

Trigonometric ratios, How do you find the ratio for these problems?

How do you find the ratio for these problems?

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