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

Algebra, prove That J[i] is an euclidean ring

prove That J[i] is an euclidean ring

Vector, uses of vector in daly life

uses of vector in daly life

More volume problems, More Volume Problems : Under this section we are de...

More Volume Problems : Under this section we are decide to take a look at several more volume problems. Though, the problems we see now will not be solids of revolution while we

Math.., how many sixs are in 60

how many sixs are in 60

Concepts, what are core concepts of marketing?

what are core concepts of marketing?

Demand Forecast, How should shoppers Stop develop its demand forecasts?

How should shoppers Stop develop its demand forecasts?

Marketing question, If a country with a struggling economy is losing the ba...

If a country with a struggling economy is losing the battle of the marketplace, should the affected government adjust its trade barriers to tilt the economic advantage of its domes

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