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

Area with polar coordinates - parametric equations, Area with Polar Coordin...

Area with Polar Coordinates In this part we are going to look at areas enclosed via polar curves.  Note also that we said "enclosed by" in place of "under" as we usually have

State test, how can i study for the math state test

how can i study for the math state test

Rounding, the number is 605176 the underline digit is 0

the number is 605176 the underline digit is 0

Partitioning -types of word problems related to subtraction, Partitioning ...

Partitioning - an action of taking away or removing some objects, and finding out how many remain. (e.g., there were 15 toffees in this container, and 10 have been eaten. How many

representative value or an extreme value, A population forms a normal dist...

A population forms a normal distribution with a mean of μ=80 and a standard deviation of o=15. For every samples, compute the z-score for the sample mean and determine whether the

Logarithms, We know that 2 4 = 16 and also that 2 is referred to as ...

We know that 2 4 = 16 and also that 2 is referred to as the base, 4 as the index or power or the exponent. The same if expressed in terms of logarithms would be log 2

Estimate the grade resistance, The grade resistance is F=W sin θ, where θ i...

The grade resistance is F=W sin θ, where θ is the grade and W is the weight of the automobile.  What is the grade resistance of a 2500 pound car traveling on a 2.6 degree uphill gr

Frequency polygon, how to compute the frequncy polygon of the scores?

how to compute the frequncy polygon of the scores?

Area of regular polygon, Suppose a  regular polygon , which is an N-sided w...

Suppose a  regular polygon , which is an N-sided with equal side lengths S and similar angles at each corner. There is an  inscribed circle  to the polygon that has center C and ba

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