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

What is the integratin of 1/sin2x?, ∫1/sin2x dx = ∫cosec2x dx = 1/2 log[cos...

∫1/sin2x dx = ∫cosec2x dx = 1/2 log[cosec2x - cot2x] + c = 1/2 log[tan x] + c Detailed derivation of ∫cosec x dx = ∫cosec x(cosec x - cot x)/(cosec x - cot x) dx = ∫(cosec 2 x

How to solving one-step equations, How to Solving One-Step Equations? E...

How to Solving One-Step Equations? Equations, where one math operation is acting on the variable, can be solved in one step. The trick is to get the variable x by itself - isol

Management, Discuss demanding total market demand verus gaing market share

Discuss demanding total market demand verus gaing market share

SOLUTIONS.., bunty and bubly go for jogging every morning. bunty goes aroun...

bunty and bubly go for jogging every morning. bunty goes around a square park of side 80m and bubly goes around a rectangular park with length 90m and breadth 60m.if they both take

Transition matrix for the probabilitiy, Suppose research on three major cel...

Suppose research on three major cell phones companies revealed the following transition matrix for the probability that a person with one cell phone carrier switches to another.

Determine the height of the washington monument, Determine the height of th...

Determine the height of the Washington Monument to the nearest tenth of a meter. a. 157.8 m b. 169.3 m c. 170.1 m d. 192.2 m c. The height of the monument is the add

Comperative statics, Discuss comparative statics,Market model and Nationa i...

Discuss comparative statics,Market model and Nationa income model

Conversion\, how many mg are there in g?

how many mg are there in g?

Distance and Section Formulae, find the coordinates of points of tri-sectio...

find the coordinates of points of tri-section of the line joining the points (-3,0) and (6,6).

Linear approximation method for interpolation, Linear Approxi...

Linear Approximation Method This is a rough and ready method of interpolation and is best used when the series moves in predicted interval

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