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

About algebra, how do i compute an algebra number

how do i compute an algebra number

What was the dow at the end of the day after the 2% drop, The Dow Jones Ind...

The Dow Jones Industrial Average fell 2% presently. The Dow began the day at 8,800. What was the Dow at the end of the day after the 2% drop? The Dow lost 2%, so it is worth 9

Absolute convergent, Find out if each of the subsequent series are absolute...

Find out if each of the subsequent series are absolute convergent, conditionally convergent or divergent. Solution: (a) The above is the alternating harmonic ser

What is the probability that the product xy less than 9, A number x is ...

A number x is selected from the numbers 1,2,3 and then a second number y is randomly selected  from  the  numbers  1,4,9. What  is  the  probability that  the product xy of the two

Finds out the center and radius of circle, Finds out the center & radius of...

Finds out the center & radius of each of the following circles & sketch the graph of the circle. a) x 2 + y 2 = 1 b) x 2 + ( y - 3) 2  = 4 Solution In all of these

How to calculate probability of event, Q. How to calculate Probability of e...

Q. How to calculate Probability of event? Ans. What chance do I have to toss the coin and get a head? You might think 50-50, 50%. What about tossing it 5 times and getting

Complex fractions, A small airplane used 5and2over3 gallons of fuel to fly ...

A small airplane used 5and2over3 gallons of fuel to fly a 2 hour trip.how many gallons were used each hour

Find the area of shaded region of circle of radius, Find the area of shaded...

Find the area of shaded region of circle of radius =7cm, if ∠AOB=70 o , ∠COD=50 o and ∠EOF=60 o . (Ans:77cm 2 ) Ans:    Ar( Sector AOB + Sector COD + Sector OEF) =  7

Find the volume of a cylinder of radius r, Find the volume of a cylinder of...

Find the volume of a cylinder of radius r and height h. Solution : Here, as we mentioned before starting this illustration we actually don't require using an integral to get t

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