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

Statistical models in simulation, Players and spectators enter a ballpark a...

Players and spectators enter a ballpark according to independent Poisson processes having respective rates 5 and 20 per hour. Starting at an arbitrary time, compute the probability

Projectile, what is the greatest projection range down an inclined plane? h...

what is the greatest projection range down an inclined plane? how we will calculate that?

Find the least number that is divisible by all numbers, Find the  leas...

Find the  least  number that  is  divisible by all  numbers between 1  and  10  (both inclusive). Ans: The required number is the LCM of 1,2,3,4,5,6,7,8,9,10 ∴ LCM = 2  × 2

Factors, write down all the factors of 36

write down all the factors of 36

Basic requirement for interpolation & extrapolation to work, What is the ba...

What is the basic requirement for both interpolation and extrapolation to work?  There must exist a functional relationship between an independent variable and a dependent variable

Solving a quadratic equation, In polynomials you have seen expressi...

In polynomials you have seen expressions of the form x 2 + 3x - 4. Also we know that when an expression is equated to zero or some other expression, we cal

Shoppers` stop, 3. How are Indian customers visiting Shoppers’ Stop any dif...

3. How are Indian customers visiting Shoppers’ Stop any different from customers of developed western countries? 4. How should Shoppers’ Stop develop its demand forecasts?

Sketch the plot first-order integrated rate, Show that the first-order inte...

Show that the first-order integrated rate expression can be written as [A] t = [A] 0 e -n(in)t where n represents the number of elapsed halftimes. Sketch the plot of [A] 1

The expected monetary value method, The expected monetary value method ...

The expected monetary value method The expected pay off as profit associated with a described combination of act and event is acquired by multiplying the pay off for that act a

Arithmetico geometric progression, find the sum of the following series upt...

find the sum of the following series upto n terms: 1*2+2*4+3*8+4*16+.....

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