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

Ann, What was last years salary if after a 3% increase the salary is 35,020...

What was last years salary if after a 3% increase the salary is 35,020?

Find the area of the rhombus, Show that the points (3, 0), (4, 5), (-1, 4) ...

Show that the points (3, 0), (4, 5), (-1, 4) and (-2, -1) taken in order are the vertices of a rhombus. Also find the area of the rhombus.

Example of multiplication of matrix, Given So calculate AB. Sol...

Given So calculate AB. Solution The new matrix will contain size 2 x 4. The entry in row 1 and column 1 of the new matrix will be determined by multiplying row 1 of

Linear algebra, solve for k such that the system 4x+ky=6 kx+y=-3

solve for k such that the system 4x+ky=6 kx+y=-3

Integrals involving roots - integration techniques, Integrals Involving Roo...

Integrals Involving Roots - Integration Techniques In this part we're going to look at an integration method that can be helpful for some integrals with roots in them. We hav

Ratio, how to make a tape diagram and a equivalent ratio

how to make a tape diagram and a equivalent ratio

Parameters of the poisson mixture model, Using R function nlm and your code...

Using R function nlm and your code from Exercise E1.2, write an R function called pois.mix.mle to obtain MLEs of the parameters of the Poisson mixture model.

Stakeholders, what is the benefit for stakeholders or disadvantage in a mon...

what is the benefit for stakeholders or disadvantage in a monoply

Parallel and perpendicular lines, The last topic that we have to discuss in...

The last topic that we have to discuss in this section is that of parallel & perpendicular lines. Following is a sketch of parallel and perpendicular lines. Suppose that th

What is transitive relations:, R is called as a transitive relation if (a, ...

R is called as a transitive relation if (a, b) € R, (b, c) € R → (a, c) € R In other terms if a belongs to b, b belongs to c, then a belongs to c.         Transitivity be uns

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