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

Definition of logarithms, Q. Definition of Logarithms? Ans. A loga...

Q. Definition of Logarithms? Ans. A logarithm to the base a of a number x is the power to which a is raised to get x. In equation format: If x = a y , then log a  x

Mode, What is the median for this problem (55+75+85+100+100)

What is the median for this problem (55+75+85+100+100)

Process for solving linear equations, 1. If the equation has any fractions ...

1. If the equation has any fractions employ the least common denominator to apparent the fractions. We will do this through multiplying both sides of the equation by the LCD. Al

Repeated roots, Under this section we will be looking at the previous case ...

Under this section we will be looking at the previous case for the constant coefficient and linear and homogeneous second order differential equations.  In this case we need soluti

Fractions, question paper on fractions

question paper on fractions

Complex Numbers, How do you compute the phase/angle of a complex number? i....

How do you compute the phase/angle of a complex number? i.e 1+2i

Progressions, We will look at three types of progressions called Ar...

We will look at three types of progressions called Arithmetic, Geometric and Harmonic Progression. Before we start looking at the intricacies of these let us unders

Calculate the probability, Coal is carried from a rrrine in West Virginia t...

Coal is carried from a rrrine in West Virginia to a power plant in New York in hopper cars on a long train. The automatic hopper car loader is set to put 36 tons of coal in each ca

Intergration, Functional and variations.Block III, Consider the functiona...

Functional and variations.Block III, Consider the functional S[y]=?_1^2 v(x^2+y'')dx , y(1)=0,y(2)=B Show that if ?=S[y+eg]-S[y], then to second order in e, ?=1/2 e?_1^2¦?g^'

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