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
Define a sparse metrics. A matrix in which number of zero entries are much higher than the number of non zero entries is known as sparse matrix. The natural method of showing m

Explain Internal and External Nodes  To  draw  the  tree's  extension  by  changing  the  empty  subtrees  by  special nodes. The  extra  nodes shown by little squares are know

Can a Queue be shown by circular linked list with only single pointer pointing to the tail of the queue? Yes a Queue can be shown by a circular linked list with only single p

Q. Explain Dijkstra's algorithm for finding the shortest path in the graph given to us.  Ans: The Dijkstra's algorithm: This is a problem which is concerned with finding

How sparse matrix stored in the memory of a computer?

How to create an General Tree and how to search general tree?

State in detail about the Integer Carrier set of the Integer ADT is the set {..., -2, -1, 0, 1, 2, ...}, and  operations on these values are addition, multiplication, subtrac

ALGORITHM (Insertion of element into a linked list) Step 1 Begin the program Step 2 if the list is empty or any new element comes before the start (head) element, then add t

Two linked lists are having information of the same type in ascending order. Write down a module to merge them to a single linked list that is sorted merge(struct node *p, stru

HOW LINKED LIST HEADER WORKS? HOW TO INSERT AND DELETE ELEMENTS IN LINKED LIST?