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

What are the three sides of a right triangle, What are the Three Sides of a...

What are the Three Sides of a Right Triangle? Each side of a right triangle can be labeled opposite, adjacent, or hypotenuse, based on its relationship to the right angle and o

What is the difference between the two models listed above?, E1) What is th...

E1) What is the difference between the two models listed above? Which is more difficult for children to understand? E2) List some activities and word problems that you would exp

Determine the second derivative of q (t ) = sec (5t ), Determine the secon...

Determine the second derivative for following functions.                             Q (t ) = sec (5t ) Solution : Following is the first derivative.              Q′ (t

Shares and dividends, A man invests rs.10400 in 6%shares at rs.104 and rs.1...

A man invests rs.10400 in 6%shares at rs.104 and rs.11440 in 10.4% shares at rs.143.How much income would he get in all?

Find the value of ((a+b)/(a-b)) , If arg (a/b) = pi/2, then find the value ...

If arg (a/b) = pi/2, then find the value of ((a+b)/(a-b)) where a,b are complex numbers. Ans) Arg (a/b) =Pi/2 Tan-1   (a/b)=   Pi/2 A/B = tanP/2 ,therefore a/b=infinity.

Compute the volume and surface area of a right circular cone, Compute the v...

Compute the volume and surface area of a right circular cone: Compute the volume and surface area of a right circular cone along with r =  3", h = 4", and l = 5".  Be sure to

What percent the girls surveyed said that area hockey sport, 450 girls were...

450 girls were surveyed about their favorite sport, 24% said in which basketball is their favorite sport, 13% said in which ice hockey is their favorite sport, and 41% said which s

Space geometry, a sketch of two dimensional system

a sketch of two dimensional system

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