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

Multiplication of two like terms with same signs, Case 1: Suppose we...

Case 1: Suppose we have two terms 7ab and 3ab. When we multiply these two terms, we get 7ab x 3ab = (7 x 3) a 1 + 1 . b 1 + 1  ( Therefore, x m . x n = x m +

Normal approximation to binomial to approximate probability, A certain flig...

A certain flight arrives on time 78% of the time. Suppose 1000 flights are randomly selected. Use the normal approximation to the binomial to approximate the probability that a)

Find how much more space than the toy it will cover, A Solid toy in the for...

A Solid toy in the form of a hemisphere surmounted by the right circular cone of height  2cm  and  diameter  of  the  base  4  cm .If  a right  circular  cylinder circumscribes the

Which of the subsequent binomials could represent the length, The area of a...

The area of a rectangle is represented through the trinomial: x 2 + x - 12. Which of the subsequent binomials could represent the length and width? Because the formula for the

Twelve coworkers go out how many slices will each person get, Twelve cowork...

Twelve coworkers go out for lunch together and sequence three pizzas. Each pizza is cut within eight slices. If each person gets the similar number of slices, how many slices will

Give the examples in real world of proportions , Give the Examples in Real ...

Give the Examples in Real World of Proportions? Proportions can be used in cooking. For example, the following is a set of ingredients for a pasta called "Spaghetti All' Amatri

Prove that ar= 3/7 ac of parallelogram , ABCD is a parallelogram in the giv...

ABCD is a parallelogram in the given figure, AB is divided at P and CD and Q so that AP:PB=3:2 and CQ:QD=4:1. If PQ meets AC at R, prove that AR= 3/7 AC. Ans:    ΔAPR ∼ Δ

Curvature, steps to trace the cartesian curve

steps to trace the cartesian curve

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