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

Complex number, The points A,B,C and D represent the numbers Z1,Z2,Z3 and Z...

The points A,B,C and D represent the numbers Z1,Z2,Z3 and Z4.ABCD is rhombus;AC=2BD.if  Z2=2+i ,Z4=1-2i,find Z1 and Z3 Ans) B(2,1) , D(1,-2) Mid Point (3/2,-1/2) Write Equati

Determinant, The subsequent topic that we require to take a look at is the ...

The subsequent topic that we require to take a look at is the determinant of a matrix. The determinant is in fact a function that gets a square matrix and converts this in a number

Matrices, suppose you a business owner and selling cloth. the following rep...

suppose you a business owner and selling cloth. the following represents the number of items sold and the cost for each item. use matrix operation to determine the total revenue ov

Calculate one-sided limits, Calculate the value of the following limits. ...

Calculate the value of the following limits. Solution From the graph of this function illustrated below, We can illustrate that both of the one-sided limits suffer

Loan amortisation problem, On 30 June 2012 Bill purchase a home by taking o...

On 30 June 2012 Bill purchase a home by taking out a 30 year mortgage of $600,000 at 6% interest per annum, compounded months. Repayments are made at the end of each month. (a) Cal

Problem solving, if you start a business and john creates 6 t shirts more t...

if you start a business and john creates 6 t shirts more than pedro and pedro four t shirts less than eva and between the three of then made 22 tshirts, how many t-shirts made each

Geometry, finding missing values from given triangle diagra m..

finding missing values from given triangle diagra m..

Exponents, i need help with exponents and how to add them

i need help with exponents and how to add them

Total accumulation of the amount deposited in saving account, A bank pays o...

A bank pays on its savings an interest rate of 6% per year but compounds interest monthly (i.e., estimates the interest each month and adds it to the balance).  You plan to deposit

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