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

Areas related to circles in mensuration, AREAS  RELATED TO CIRCLES The...

AREAS  RELATED TO CIRCLES The  mathematical  sciences particularly  exhibit  order,  symmetry,  and limitation;  and  these  are the  greatest  forms  of the beautiful. In t

Calculate zeros in the denominator of rational expressions, About Zeros in ...

About Zeros in the Denominator of Rational Expressions One thing that you must be careful about when working with rational expressions is that the denominator can never be zero

Absolute mean deviation-measures of central tendency, Illustration 1 I...

Illustration 1 In a described exam the scores for 10 students were given as: Student Mark (x) |x-x¯| A 60

Implement immutable data type rational for rational number, Implement an im...

Implement an immutable data type Rational for rational numbers that supports addition, subtraction, multiplication and division. public class Rational Ration

Differential equations, Find the normalized differential equation which has...

Find the normalized differential equation which has {x, xex} as its fundamental set

Substitution rule, Substitution Rule ∫ f ( g ( x )) g′ ( x ) dx = ∫ f (...

Substitution Rule ∫ f ( g ( x )) g′ ( x ) dx = ∫ f (u ) du,     where, u = g ( x ) we can't do the following integrals through general rule. This looks considerably

Find out equation is a function, Example: Find out which of the following ...

Example: Find out which of the following equations functions are & which are not functions.                            y= 5x + 1 Solution The "working" definition of fu

RECTILINEAR FIGURES, AB,BC,CD ARE THREE CONSECUTIE SIDES OF REGULAR POLYGON...

AB,BC,CD ARE THREE CONSECUTIE SIDES OF REGULAR POLYGON.IF ANGLE BAC IS 18 DEGREE, FIND EXTERIOR ANGLES AND NUMBER OF SIDES ?

Square the next consecutive integer find the lesser integer, The square of ...

The square of one integer is 55 less than the square of the next consecutive integer. Find the lesser integer. Let x = the lesser integer and let x + 1 = the greater integer. T

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