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".     

Ans:

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 driver takes shortest possible route to attain destination. The problem which we will discuss here is similar to this type of finding shortest route in any specific graph. The gr

Explain the Abstract data type assertions Generally, ADT assertions translate into assertions about the data types which implement ADTs, which helps insure that our ADT impleme

QUESTION (a) Construct a binary tree for the following numbers assuming that a number greater than the node (starting from the root) goes to the left else it goes to the right.

Program for Linear Search. Program: Linear Search /*Program for Linear Search*/ /*Header Files*/ #include #include /*Global Variables*/ int search; int

Which data structure is required to change infix notation to postfix notation?    Stack function is used to change infix notation to postfix notatio n

The complexity Ladder: T(n) = O(1). It is called constant growth. T(n) does not raise at all as a function of n, it is a constant. For illustration, array access has this c

Big oh notation (O) : The upper bound for the function 'f' is given by the big oh notation (O). Considering 'g' to be a function from the non-negative integers to the positive real

how to learn about time complexity of a particular algorithm

Write an algorithm, using a flowchart, which inputs the heights of all 500 students and outputs the height of the tallest person and the shortest p erson in the school.

Using stacks, write an algorithm to determine whether the infix expression has balanced parenthesis or not Algorithm parseparens This algorithm reads a source program and