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

Find the area of shaded region, Find the area of shaded region, if the side...

Find the area of shaded region, if the side of square is 28cm and radius of the sector is ½ the length of side of square.

Equation of a straight line, In a two dimensional case, the form of t...

In a two dimensional case, the form of the linear function can be obtained if we know the co-ordinates of two points on the straight line. Suppose  x' and  x"  are two

Multiplication rule: dependent events, Multiplication Rule: Dependent Event...

Multiplication Rule: Dependent Events The joint probability of two events A and B which are dependent is equal to the probability of A multiplied by the probability of B given

Example of multiplying decimals, Example of Multiplying Decimals: Exa...

Example of Multiplying Decimals: Example:  0.45 x 10 = 4.5.  Same, while multiplying a decimal through 100, 1000, and 10,000, move the decimal point to the right the similar

Determine the properties and query are definable in datalog, We now focus o...

We now focus on the use of Datalog for defining properties and queries m graphs. (a) Suppose that P is some property of graphs definable in Datalog. Show drat P is preserved und

Scale Drawing, Model of 180 meter tall building using a scale of 1.5 centim...

Model of 180 meter tall building using a scale of 1.5 centimeters = 3.5 meters. How tall will the model be?

Four distinct points on a circle, If (a,1/a), (b,1/b),(c,1/c),(d,1/d) are f...

If (a,1/a), (b,1/b),(c,1/c),(d,1/d) are four distinct points on a circle of radius 4 units then,abcd is equal to??   Ans) As they are of form (x,1/x) let eq of circle be x

Comparison test - sequences and series, Comparison Test Assume that we...

Comparison Test Assume that we have two types of series ∑a n and ∑b n with a n , b n ≥ 0 for all n and a n ≤ b n for all n.  Then, A.  If ∑b n is convergent then t

Evaluate the limit, Evaluate the given limit. Solution : It is a ...

Evaluate the given limit. Solution : It is a combination of many of the functions listed above and none of the limited are violated so all we have to do is plug in x = 3

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