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

Functions of many variables, There may be more than one independent v...

There may be more than one independent variable which determines the value of y. The dimension of a function is determined by the number of independent variables in the

Proof by Condratiction, "Prove by contradiction that no root of the equatio...

"Prove by contradiction that no root of the equation x^18 -2x^13 + x^5 -3x^3 + x - 2 = 0 is an integer divisible by 3" Any help would be very much appreciated!

Problem solver, a bathroom measure 250 cm by 175 cm calculate the side of t...

a bathroom measure 250 cm by 175 cm calculate the side of the largest square tile that can tile the floor

Calculate the number-average and weight-average molar mass, Three mixtures ...

Three mixtures were prepared with very narrow molar mass distribution polyisoprenesamples with molar masses of 8000, 25,000, and 100,000 as indicated below. (a) Equal numbers of

Postage stamp problem, Explain Postage Stamp Problem solving tehcnique? Wha...

Explain Postage Stamp Problem solving tehcnique? What is Postage Stamp Problem?

Find the sum of all natural no. between 101 and 304, Find the sum of all na...

Find the sum of all natural no. between 101 & 304 which are divisible by 3 or 5. Find their sum. Ans:    No let 101 and 304, which are divisible by 3. 102, 105..........

What is the larger dimension in inches of the frame, Jessica has a picture ...

Jessica has a picture in a frame with a total area of 288 in2. The dimension of the picture without the frame is 12 in through 14 in. What is the larger dimension, in inches, of th

Relationship between the shortest path distances - tree, 1. a)  Given a dig...

1. a)  Given a digraph G = (V,E), prove that if we add a constant k to the length of every arc coming out from the root node r, the shortest path tree remains the same.  Do this by

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