A tree having ''m'' nodes has (m-1) branches. prove., Data Structure & Algorithms

Q. Prove the hypothesis that "A tree having 'm' nodes has exactly (m-1) branches".     


A tree having m number of nodes has exactly (m-1) branches

Proof: A root in a tree has indegree zero and all other nodes have indegree one. There must be (m-1) incoming arcs to the (m-1) non-root nodes. If there is any other arc, this arc must be terminating at any of the nodes. If the node is root, then its indegree will become one and that is in contradiction with the fact that root always indegree zero. If the end point of this extra edge

is any non-root node then its indegree will be two, which is again a contradiction. Hence there cannot be more arcs. Therefore, a tree with m vertices will have exactly (m-1) edges.



Posted Date: 7/11/2012 1:36:54 AM | Location : United States

Related Discussions:- A tree having ''m'' nodes has (m-1) branches. prove., Assignment Help, Ask Question on A tree having ''m'' nodes has (m-1) branches. prove., Get Answer, Expert's Help, A tree having ''m'' nodes has (m-1) branches. prove. Discussions

Write discussion on A tree having ''m'' nodes has (m-1) branches. prove.
Your posts are moderated
Related Questions
A full binary tree with 2n+1 nodes have n non-leaf nodes

How can we convert a graph into a tree ? Do we have any standardized algorithm for doing this?

Explain in brief about the Container An entity which holds finitely many other entities. Just as containers such as boxes, baskets, bags, pails, cans, drawers, and so for

Q. What do you understand by the term sparse matrix? How sparse matrix is stored in the memory of a computer? Write down the function to find out the transpose of a sparse matrix u

Q. Explain the basic concept of the primitive data structures.                                             Ans. The concept of P r i m i t i ve Data

Illustrate the Visual realism applications a)   Robot Simulations : Visualization of movement of their links and joints  and end effector movement etc. b)  CNC programs ver

In this project you will write a program to produce a discrete time simulation of a queue as shown in Fig. 1. Time is slotted on the input and the output. Each input packet follows

Design  and implement  an algorithm  to simulate car  re-organizing of the train at the railway switching junction. You can only use stacks as the data structure to represent the t

Worst Fit method:- In this method the system always allocate a portion of the largest free block in memory. The philosophy behind this method is that by using small number of a ve

Q. Write  down the  algorithm  to  insert  an  element  to  a  max-heap  which  is  represented sequentially.           Ans: The algorithm to insert an element "newkey" to