Prove that a tree with n vertices has n - 1 edges, Mathematics

Assignment Help:

Prove that A tree with n vertices has (n - 1) edges.   

Ans: From the definition of a tree a root comprise indegree zero and all other nodes comprise indegree one. There should be (n - 1) incoming arcs to the (n - 1) non-root nodes. If there is any another arc, this arc should be terminating at any of the nodes. If the node is root, after that its indegree will become one and that is in contradiction along with the fact that root all time has indegree zero. If the end point of this extra edge is any non-root node after that its indegree will be two, which is once again a contradiction. Therefore there cannot be more arcs. Hence, a tree of n vertices will have exactly (n - 1) edges.


Related Discussions:- Prove that a tree with n vertices has n - 1 edges

Stats, Instructions: 1. Write the null and alternative hypotheses. ...

Instructions: 1. Write the null and alternative hypotheses. 2. Calculate the test statistic. 3. Determine the critical value whether or not there has been an improv

Easy math margin percentage increase, If A = 100 and B = 44 then A1 =...

If A = 100 and B = 44 then A1 = 120 and B2 = 52.80 A is MAP and B is Tier 6. I need help to find a simple equation that I just cannot find. I just need the percentage

Find the sum of given equation upto n limit, Find the sum of (1 - 1/n ) + (...

Find the sum of (1 - 1/n ) + (1 - 2/n ) + (1 - 3/n ) ....... upto n terms. Ans: (1 - 1/n ) + (1 - 2/n ) - upto n terms   ⇒[1+1+.......+n terms] - [ 1/n + 2/n +....+

Linear programming , Use the simplex method to solve the following LP Probl...

Use the simplex method to solve the following LP Problem. Max Z = 107x1+x2+2x3 Subject to 14x1+x2-6x3+3x4=7 16x1+x2-6x3 3x1-x2-x3 x1,x2,x3,x4 >=0

Geometria, un prisma retto ha per base un rombo avente una diagonale lunga ...

un prisma retto ha per base un rombo avente una diagonale lunga 24cm. sapendo che la superficie laterale e quella totale misurano rispettivamente 2800cm e3568cm ,calcola la misura

Mensuration, A palm tree of heights 25m is broken by storm in such a way th...

A palm tree of heights 25m is broken by storm in such a way that its top touches the ground at a distance of 5m from its root,but is not separated from the tree.Find the height at

Curve tracing, how to curve trace? and how to know whether the equation is ...

how to curve trace? and how to know whether the equation is a circle or parabola, hyperbola ellipse?

Probability - applications of integrals, Probability - Applications of inte...

Probability - Applications of integrals In this final application of integrals that we'll be looking at we are going to look at probability.  Previous to actually getting into

Critical points, Critical Point Definition : We say that x = c is a critic...

Critical Point Definition : We say that x = c is a critical point of function f(x) if f (c) exists & if either of the given are true. f ′ (c ) = 0        OR             f ′ (c

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