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

Logarithm functions, Logarithm Functions : In this section we'll discuss l...

Logarithm Functions : In this section we'll discuss look at a function which is related to the exponential functions we will learn logarithms in this section. Logarithms are one o

Ravens played 25 home games how many games did they win, The Ravens played ...

The Ravens played 25 home games this year. They had 9 losses and 2 ties. How many games did they win? Eleven games are accounted for along with the losses and ties (9 + 2 = 11)

Solid Mensuration, The two sides of a triangle are 17 cm and 28 cm long, an...

The two sides of a triangle are 17 cm and 28 cm long, and the length of the median drawn to the third side is equal to 19.5 cm. Find the distance from an endpoint of this median to

Estimates the probabilities of price changes, Mr. Hoper is in charge of inv...

Mr. Hoper is in charge of investments for the golden horizon company. He estimates from past price fluctuations in the gold market that the probabilities of price changes on a give

Pre Calculus 12, A radioactive substance decays to 30% of its original mass...

A radioactive substance decays to 30% of its original mass in 15 months. Determine the half-life of this radioactive substance to the nearest month

Decmiels, how do you re name percents to decimal

how do you re name percents to decimal

Simultaneous equations, i need a step by step guide to answering simultaneo...

i need a step by step guide to answering simultaneous equation for gcses

Quadratic equation modeling profitability, Sam''s sport''s equipment sells ...

Sam''s sport''s equipment sells footballs. They maximized their profitability last year at (6,4) where x represents employees and P(x) represents profitability. Sam noticed that wh

Experiments probabillity of compound events, what is the expiremental proba...

what is the expiremental probability that the next toss and spin will result in 3 and tail if 1-heads,53.2-heads,49.3-heads,54.1-tail,65.2-tails,71.3-tails,62

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