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

Find out the average temperature, Find out the average temperature: E...

Find out the average temperature: Example: Find out the average temperature if the subsequent values were recorded: 600°F, 596°F, 597°F, 603°F Solution: Step

Naive regular perturbation of the form, Consider the equation e x 3 + ...

Consider the equation e x 3 + x 2 - x - 6 = 0, e > 0 (1) 1. Apply a naive regular perturbation of the form do derive a three-term approximation to the solutions

How to converting scientific notation to standard notation , How to Convert...

How to Converting Scientific Notation to Standard Notation ? To change a number in scientific notation to standard notation, move the decimal point the same number of places as

Sequence-or-series, in and ap 1,2,3,4,5,6,7,8,9 11,12,13,14,15,16,17,18,19...

in and ap 1,2,3,4,5,6,7,8,9 11,12,13,14,15,16,17,18,19 and like that nonzzero digit find tn Solution) First break the ''n'' number in terms of 10''s power. For e.g if n=3259 wri

Applied mathematics, I have a journal article in applied mathematics and wa...

I have a journal article in applied mathematics and want to analyze the solutions step by step. Is there anyone specialize in this file?

Probability: determine the optimal strategy , On a picnic outing, 2 two-pe...

On a picnic outing, 2 two-person teams are playing hide-and-seek. There are four  hiding locations (A, B, C, and D), and the two members of the hiding team can hide separately in a

The appropriate resource constraint, Consider a person's decision problem i...

Consider a person's decision problem in trying to decide how many children to have. Although she cares about children and would like to have as many as possible, she knows that chi

Evaluate the volume of a basketball along with the volume, Dawn wants to ev...

Dawn wants to evaluate the volume of a basketball along with the volume of a tennis ball. Which formula will she use? The volume of a sphere is 4/3 times π times the radius cub

Determine the domain of the function, Determine or find out the domain of t...

Determine or find out the domain of the subsequent function. r → (t) = {cos t, ln (4- t) , √(t+1)} Solution The first component is described for all t's. The second com

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