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

Compute the derivative, Write an octave program that will take a set of poi...

Write an octave program that will take a set of points {x k , f k } representing a function and compute the derivative at the same points x k using 1. 2-point forward di erence

Set theory, how to prove Decidability Theorem of Logic

how to prove Decidability Theorem of Logic

SIMPLE INTEREST, A payday loan company charges a $95 fee for a $500 payday ...

A payday loan company charges a $95 fee for a $500 payday loan that will be repaid in 11 days. Treating the fee as interest paid, what is the equivalent annual interest rate?

State demorgans law and prove it using the truth table, State DeMorgan's la...

State DeMorgan's law. Prove it using the truth table.   Ans: DeMorgan's law defines that    (i)  (x ∨ y)' = x' ∧ y' (ii)  (x ∧ y)' = x' ∨ y'      Now let us dr

What is factoring of polynomials, What is Factoring of Polynomials? Fac...

What is Factoring of Polynomials? Factoring means much the same thing for polynomials as it does for integers. When you multiply several polynomials together, The polyn

Algebra function., problem to understand an problem; f(X-2)=X+3 / X-4

problem to understand an problem; f(X-2)=X+3 / X-4

Prove asymptotic bounds for recursion relations, 1. (‡) Prove asymptotic b...

1. (‡) Prove asymptotic bounds for the following recursion relations. Tighter bounds will receive more marks. You may use the Master Theorem if it applies. 1. C(n) = 3C(n/2) + n

How much, If one acre costs $2500 how much does .39 of an acre cost

If one acre costs $2500 how much does .39 of an acre cost?

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