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

Geometric applications to the cross product, Geometric Applications to the ...

Geometric Applications to the Cross Product There are a so many geometric applications to the cross product also.  Assume we have three vectors a → , b → and c → and we make

Unit circle, Unit circle: The unit circle is one of the most valuable tool...

Unit circle: The unit circle is one of the most valuable tools to come out in trig.  Unluckily, most people don't study it as well. Below is the unit circle with just the first

Find the straight distance between a and b, There is a staircase as shown i...

There is a staircase as shown in figure connecting points A and B. Measurements of steps are marked in the figure. Find the straight distance between A and B. (Ans:10) A ns

Proof of the derivative of a constant, Proof of the Derivative of a Constan...

Proof of the Derivative of a Constant : d(c)/dx = 0 It is very easy to prove by using the definition of the derivative therefore define, f(x) = c and the utilize the definiti

Factoring out the greatest common factor, Factoring out the greatest common...

Factoring out the greatest common factor of following polynomials.                    8x 4 - 4 x 3 + 10 x 2  Solution Primary we will notice that we can factor out a

How many people are usual to vote for mr salva on survey, The Daily News re...

The Daily News reported that 54% of people surveyed said in which they would vote for Larry Salva for mayor. Based on the survey results, if 23,500 people vote in the election, how

Mixing problems, Let's start things by searching for a mixing problem.  Pre...

Let's start things by searching for a mixing problem.  Previously we saw these were back in the first order section. In those problems we had a tank of liquid with several kinds of

Problems involving motion - word problems, Problems Involving Motion - Word...

Problems Involving Motion - Word Problems: How far can a car travelling at a rate of 52 miles per hour travel in 2½ hours? Solution: Using Equation 13: s = vavt

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