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

Transition matrix for the probabilitiy, Suppose research on three major cel...

Suppose research on three major cell phones companies revealed the following transition matrix for the probability that a person with one cell phone carrier switches to another.

Solving a quadratic equation, In polynomials you have seen expressi...

In polynomials you have seen expressions of the form x 2 + 3x - 4. Also we know that when an expression is equated to zero or some other expression, we cal

Integration, Awhat is the meaning and application sk question #Minimum 100 ...

Awhat is the meaning and application sk question #Minimum 100 words accepted#

Whole numbers, Observe that natural numbers do not have a zero....

Observe that natural numbers do not have a zero. This shortcoming is made good when we consider the set of whole numbers. The set of whole numbe

Binomial mathematical properties, Binomial Mathematical Properties 1. ...

Binomial Mathematical Properties 1. The expected or mean value = n × p = np Whereas; n = Sample Size p = Probability of success 2. The variance = npq Whereas; q =

Ineqaulites, how to work out inequalities with negative signs?

how to work out inequalities with negative signs?

BASIC MATHEMATHICS :AN APPLIED APPROACH BY RATHUS, FIRST OF ALL I WANNA KN...

FIRST OF ALL I WANNA KNOW THECHNIQUES, I CAT DIVIDE BIG BIG NUMBERS , EVERYTHING IN MATH IIS VERY HARD FOR ME I HOPE YOU CAN HELP ME

Extreme value theorem, Extreme Value Theorem : Assume that f ( x ) is cont...

Extreme Value Theorem : Assume that f ( x ) is continuous on the interval [a,b] then there are two numbers a ≤ c, d ≤ b so that f (c ) is an absolute maximum for the function and

Integers, Explain with the help of number line (-6)+(+5)

Explain with the help of number line (-6)+(+5)

Proof of sum-difference of two functions, Proof of Sum/Difference of Two Fu...

Proof of Sum/Difference of Two Functions : (f(x) + g(x))′  = f ′(x) +  g ′(x)  It is easy adequate to prove by using the definition of the derivative.  We will start wi

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