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

How much will she owe the fabulous fence company, Kelly plans to fence in h...

Kelly plans to fence in her yard. The Fabulous Fence Company charges $3.25 per foot of fencing and $15.75 an hour for labor. If Kelly requires 350 feet of fencing and the installer

Direction fields in newtons law, One of the simplest physical situations to...

One of the simplest physical situations to imagine of is a falling object. Thus let's consider a falling object along with mass m and derive a differential equation as, when resolv

Integerts, how do u add and subtract integers

how do u add and subtract integers

Bernoulli differential equations, In this case we are going to consider dif...

In this case we are going to consider differential equations in the form, y ′ +  p   ( x ) y =  q   ( x ) y n Here p(x) and q(x) are continuous functions in the

Example of inflection point-differential equation, Example of inflection po...

Example of inflection point Determine the points of inflection on the curve of the function y = x 3 Solution The only possible inflexion points will happen where

Upper limit of normal , Frequently, tests that yield abnormal results are r...

Frequently, tests that yield abnormal results are repeated for confirmation.  What is the probability that for a usual person a test will be at least 1.5 times as high as the upper

What is stem-and-leaf plots, Q. What is Stem-and-Leaf Plots? Ans. ...

Q. What is Stem-and-Leaf Plots? Ans. A stem-and-leaf plot is a table that provides a quick way to arrange a set of data and view its shape, or distribution. Each data val

Squeeze theorem (sandwich theorem and the pinching theorem), Squeeze Theore...

Squeeze Theorem (Sandwich Theorem and the Pinching Theorem) Assume that for all x on [a, b] (except possibly at x = c ) we have,                                 f ( x )≤ h (

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