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

Quadratic equation assignment, what is number of quadratic equation that ar...

what is number of quadratic equation that are unchanged by squaring their roots is There are four such cases x 2   =0 root 0 (x-1) 2 =0  root 1 x(x+1)=0  roots  0 and 1

Circles - common polar coordinate graphs, Circles - Common Polar Coordinate...

Circles - Common Polar Coordinate Graphs Let us come across at the equations of circles in polar coordinates. 1. r = a . This equation is saying that there is no matter

Understanding Logistics, How can i get a better understanding of logistics ...

How can i get a better understanding of logistics without having a degree on logistics and knowledge of it? Simply, in a very basic form..

Find out the determinant, Find out the determinant: Find out the deter...

Find out the determinant: Find out the determinant of the following 3 x 3 matrix, expanding about row 1. Solution:

Probability, TWO PERSONS A AND B AGREE TO MEET AT A PLACE BTWEEN 11 TO 12 N...

TWO PERSONS A AND B AGREE TO MEET AT A PLACE BTWEEN 11 TO 12 NOON.  THE FIRST ONE TOARRIVE WAITS FOR 20 MIN AND THEN LEAVE. IF THE TIME OF THIR ARRIVAL BE INDEPENDET AND AT RNDOM,T

Circle, a wheel revolves 360 deegre revolution in one minute .Find how many...

a wheel revolves 360 deegre revolution in one minute .Find how many radians will the wheel subtend in one second

Elps in maths, 25 cookies have to be divided equally among 4 children.hw ca...

25 cookies have to be divided equally among 4 children.hw can we use elps to answer this question?

Factorization, factorize the following algebraic expressions

factorize the following algebraic expressions

What is unreducing fractions, Q, Did you know that you can unreduce a fract...

Q, Did you know that you can unreduce a fraction? Ans. Remember, you reduce a fraction by dividing the numerator and denominator by the same numbers. Here we divide

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