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.