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 are length and sketch the level curves, 1) Find the are length of ...

1) Find the are length of r(t) = ( 1/2t^2, 1/3t^3, 1/3t^3) where t is between 1 and 3 (greater than or equal less than or equal) 2) Sketch the level curves of f(x,y) = x^2-2y^2

Solve the subsequent differential equation, Solve the subsequent differenti...

Solve the subsequent differential equation. 2xy - 9 x 2 + (2y + x 2 + 1) dy/dt = 0 Solution Let's start off via supposing that wherever out there in the world is a fun

Higher-order derivatives, Higher-Order Derivatives It can be se...

Higher-Order Derivatives It can be seen that the derivative of a function is also a function. Considering f'x as a function of x, we can take the derivative

Circle, prove the the centre of a circle is twice of reference angle

prove the the centre of a circle is twice of reference angle

Concept, uses of maths concept

uses of maths concept

Geometry, what is the product of the solutions to the equation: x2+4x=-4

what is the product of the solutions to the equation: x2+4x=-4

Explain the vertex formula, Explain the Vertex Formula ? The vertex for...

Explain the Vertex Formula ? The vertex formula is a convenient way of finding the vertex of the graph for any quadratic function. The graph of the quadratic equation f(x) = ax

Illustrate median with example, Q. Illustrate Median with example? Ans...

Q. Illustrate Median with example? Ans. The median of a data set is the middle value (or the average of the two middle terms if there are an even number of data values) wh

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