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

Profit and loss, a man buy car at rs.50 and sells it at gain of 14% find ...

a man buy car at rs.50 and sells it at gain of 14% find the sp

Nonhomogeneous differential equations, Let's here start thinking regarding ...

Let's here start thinking regarding that how to solve nonhomogeneous differential equations.  A second order, linear non-homogeneous differential equation is as y′′ + p (t) y′ +

Find the maximum expected holdings, Problem: A person has 3 units of mo...

Problem: A person has 3 units of money available for investment in a business opportunity that matures in 1 year. The opportunity is risky in that the return is either double o

Decimals, what is 0.875 of 2282?

what is 0.875 of 2282?

Linear programming, As office manager of her firm, Marcellyne has been dir...

As office manager of her firm, Marcellyne has been directed to buy new filing cabinets. She knows that cabinet A costs $10, requires 6 square feet of floor space, and holds 9 cubic

Equilibrium solutions, In the earlier section we modeled a population depen...

In the earlier section we modeled a population depends on the assumption that the growth rate would be a constant. Though, in reality it doesn't make much sense. Obviously a popula

Matric, fgdg ggghfr hhrhfrf hfrrg jhj hjgg dear friend ghr tu vgu jyyiu ui ...

fgdg ggghfr hhrhfrf hfrrg jhj hjgg dear friend ghr tu vgu jyyiu ui u huik bgyuiiyts husk

What is the ratio of the areas of sectors , What is the ratio of the areas ...

What is the ratio of the areas of sectors I and II ?                               (Ans:4:5) Ans:    Ratio will be 120/360  Π r 2 : 150/360  Π r 2 4/12  : 5/12  =

How many times must he mow across the width of the lawn, Allan has been hir...

Allan has been hired to mow the school soccer field that is 180 ft wide through 330 ft long. If his mower mows strips which are 2 feet huge, how many times must he mow across the w

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