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 the limit of given matrix, What is required: This assignment is to be ...

What is required: This assignment is to be resolved using Maple. You are to upload a single Maple worksheet with file name FamilynameFirstname.mw (e.g., CarrElliot.mw), using the A

Linear Equations, y= -3x tell if it is linear or not. our teacher wants it ...

y= -3x tell if it is linear or not. our teacher wants it graphed or something.

Applications of rational numbers, Kaylee makes 56 packages in seven hours T...

Kaylee makes 56 packages in seven hours Taylor makes 20% more packages in nine hours who makes more packages per hour

Area of the equilateral triangle, Area of the equilateral triangle: ...

Area of the equilateral triangle: Given : D, E, F are the mind points of BC, CA, AB. R.T.P. : We have to determine the ratio of the area of of triangle DEF and triangle AB

Determine how many valid fortran identifiers, A valid identifier in the pro...

A valid identifier in the programming language FORTAN contains a string of one to six alphanumeric characters (the 36 characters A, B,...., Z, 0, 1,...9) starting with a letter. De

Right angle triangle, If the points for a right angle triangle are XYZ wher...

If the points for a right angle triangle are XYZ where do I mark the points?

Introduction to learning to count, INTRODUCTION : Most of us, when plannin...

INTRODUCTION : Most of us, when planning the first mathematical experience for three-year olds, think in terms of helping them memorise numbers from 1 to 20. We also teach them to

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