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

Applications of derivatives, Applications of derivatives : At last, let's ...

Applications of derivatives : At last, let's not forget about our applications of derivatives. Example    Assume that the amount of air in a balloon at any time t is specified

Break even point, what is break even point and how can it helps managers to...

what is break even point and how can it helps managers to make decisions?

Money, What is the formulate of finding commission

What is the formulate of finding commission

Factoring polynomials, Factoring polynomials is probably the most important...

Factoring polynomials is probably the most important topic. We already learn factor of polynomial .If you can't factor the polynomial then you won't be able to even start the probl

Triangulos rectangulos y no rectangulos, el extremo de un poste que partió ...

el extremo de un poste que partió 8.45 metros de la base del poste y forma con el suelo un angulo de 40 grados 28 minutos.hallar la altura original del poste

What will the day of the week be the further time at the gym, Max goes to t...

Max goes to the gym every fourth day. Ellen's exercise routine is to go every third day. Today is Monday and both Max and Ellen are at the gym. What will the day of the week be the

Determine the number of full withdrawals, A worker retires with a lump sum ...

A worker retires with a lump sum superannuation benefit of $500,000. She immediately invests this money in a fund earning 5% pa effective. One year after retirement she begins maki

Find out the linear approximation, Find out the linear approximation for a...

Find out the linear approximation for at x =8 .  Utilizes the linear approximation to approximate the value of  and Solution Since it is just the tangent line there

Integration by parts -integration techniques, Integration by Parts -Integra...

Integration by Parts -Integration Techniques Let's start off along with this section with a couple of integrals that we should previously be able to do to get us started. Fir

Customer arithmetics, what is $6500 jamaican dollars in european money if ...

what is $6500 jamaican dollars in european money if jamaican $160.13 = 1 european money

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