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

probability that the card is a 8 or an ace, A standard deck of cards conta...

A standard deck of cards contains 52 cards. One card is selected at random. Determine a)    The probability that the card is a 8 or an Ace? b)    The probability that the card is

What is the total balance of an account after 18 months, A certain bank pay...

A certain bank pays 3.4% interest per year for a certificate of deposit, or CD. What is the total balance of an account after 18 months along with an initial deposit of $1,250?

Project, report on shares and dovidend using newspaer

report on shares and dovidend using newspaer

Find the integral of a function, We want to find the integral of a function...

We want to find the integral of a function at an arbitrary location x from the origin. Thus, where I(x=0) is the value of the integral for all times less than 0. (Essenti

3-d coordinate system - three dimensional spaces, The 3-D Coordinate System...

The 3-D Coordinate System We will start the chapter off with a quite brief discussion introducing the 3-D coordinate system and the conventions that we will be utilizing.  We

What is probability that a person selected at random eyes, If 65% of the po...

If 65% of the populations have black eyes, 25% have brown eyes and the remaining have blue eyes. What is the probability that a person selected at random has (i) Blue eyes (ii) Bro

Local maxima, Given that f(x,y) = 3xy -  x 2 y  - xy 2 . Fi nd all the poin...

Given that f(x,y) = 3xy -  x 2 y  - xy 2 . Fi nd all the points on the surface z = f(x, y)where local maxima, local minima, or saddles occur

Find the ratio of line segment, Find the ratio in which the line segment jo...

Find the ratio in which the line segment joining A(6,5) and B(4,-3) is divided by the line y=2           (Ans:3:5) Ans :   Let the ratio be k:1 x = 4 k + 6/ k +1 y

Proof of the properties of vector arithmetic, Proof of the Properties of ve...

Proof of the Properties of vector arithmetic Proof of a(v → + w → ) = av → + aw → We will begin with the two vectors, v → = (v 1 , v 2 ,..., v n )and w? = w

What is the area of the court in square feet, A racquetball court is 40 ft ...

A racquetball court is 40 ft through 20 ft. What is the area of the court in square feet? The area of a rectangle is length times width. Thus, the area of the racquetball court

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