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

Tangents, two circle of radius of 2cm &3cm &diameter of 8cm dram common tan...

two circle of radius of 2cm &3cm &diameter of 8cm dram common tangent

Stuck on this, I need help on radical notation for a homework assignment I'...

I need help on radical notation for a homework assignment I''m really confused on it. Can I get help?

Lower than average, A local police precinct has seen a recent enhance in th...

A local police precinct has seen a recent enhance in the number of complaints filed regarding how officers are interacting with the public. Before addressing the issue, the command

Shares and dividend, what all can be the table contents for my maths projec...

what all can be the table contents for my maths project on shares and dividend

If a sequence is bounded and monotonic then it is convergent, Theorem ...

Theorem If {a n } is bounded and monotonic then { a n } is convergent.  Be cautious to not misuse this theorem.  It does not state that if a sequence is not bounded and/or

Regarding submitting sample work, How can I submit a sample of my work in e...

How can I submit a sample of my work in either teaching online or checking homework as I am retired and doing this for the first time?

Find the shortest length of wire needed, A 125-foot tower is located on the...

A 125-foot tower is located on the side of a mountain that is inclined at 32° to the horizontal. A guy wire is to be fitted to the top of the tower and anchored at a point 55 feet

Queuing Theory, A telephone exchange has two long distance operators.The te...

A telephone exchange has two long distance operators.The telephone company find that during the peak load,long distance calls arrive in a poisson fashion at an average rate of 15 p

Find out the length of hamiltonian path, Find out the length of Hamiltonian...

Find out the length of Hamiltonian Path in a connected graph of n vertices. Ans: The length of Hamiltonian Path in a connected graph of n vertices is n-1.

Book 6b, one bathroom is 0.3m long how long is a row of 8 tiles

one bathroom is 0.3m long how long is a row of 8 tiles

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