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

Binormal vector - three dimensional space, Binormal Vector - Three Dimensio...

Binormal Vector - Three Dimensional Space Next, is the binormal vector.  The binormal vector is illustrated to be, B → (t) = T → (t) * N → (t) Since the binormal vecto

Concept, uses of maths concept

uses of maths concept

Decision tree analysis, DECISION TREE ANALYSIS The Finance Manager of ‘...

DECISION TREE ANALYSIS The Finance Manager of ‘Softy’ baby soap manufacturing company being successful in the first two years of the company’s operations is considering to set

The perimeter of a rectangle is 104 inches find out width, The perimeter of...

The perimeter of a rectangle is 104 inches. The width is 6 inches less than 3 times the length. Find out the width of the rectangle. Let l = the length of the rectangle and let

Explain angle pairs, Explain angle pairs ? Adjacent angle pairs Two an...

Explain angle pairs ? Adjacent angle pairs Two angles are adjacent if they: 1. Have the same vertex. 2. Share a common side. 3. Have no interior points in common. Definit

Find the distance of the bird from the girl, A boy standing on a horizontal...

A boy standing on a horizontal plane finds a bird flying at a distance of 100m from him at an elevation of 300. A girl standing on the roof of 20 meter high building finds the angl

Algebra, how do you work out algebra

how do you work out algebra

Power series and functions - sequences and series, Power Series and Functio...

Power Series and Functions We opened the previous section by saying that we were going to start thinking about applications of series and after that promptly spent the section

Math homework help, I need help witth my homework can you help please

I need help witth my homework can you help please

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