Number of inner nodes in relation to the leaf number N

Question

I am aware that if there is a bifurcating tree with N leaves, then there are (N-1) internal nodes (branching points) with a single root node. How is this relationship proved?

Best,

Answer 1

I did it myself, the base case

n1 is n=2 2-1=1, 

n2 is n=3 3-1=2. 

n(k) is n=k k-1=k-1; n

n(k+1) is n=k+1 (k+1)-1=(k-1)+1=n(k)+1

Since the k+1 step relies and follows from the k step the base case can be reached.

best,

based on a comment below (by Steven Stadnicki), some insigt into the process the induction is based upon is needed to make this complete which is correct. The process is that with the basic tree n1, to add another internal node, a leaf node is replaced by an internal node (-1) and has then two leaves attached to the new internal node (+2) for a total of (+1) from the alteration of adding another internal node. So the addition of an internal node and leaf node is 1 to 1, but the initial offset with there being 1 internal to 2 leaf nodes remains. Therefore we can easily see how the individual induction steps work and n-1 is the relationship that hold.>>>>

Answer 2

I think the easiest way it to regard this a knock-out competition with $n$ teams, each inner node is a match, and there is one winner. So there are $n-1$ teams to knock out and so $n-1$ nodes.

Or you could do it by induction noting that replacing a pair of leaves and an inner node by a leaf reduces the number of inner nodes and leaves by 1, and that if there is only one leaf then there is no inner node.

Answer 3

Here is an approach considering a directed binary tree:

Let there be $k$ internal nodes (Note that we consider the root to be an internal node as well). Since we consider a binary tree, the $k$ internal nodes contributes 2 edges each and thus we have $2k$ many edges in the tree that implies there is a total degree of $4k$ considering all the edges in the tree.

Now it is clear that for each such edge at least one of them (precisely all the outgoing edges of the internal nodes) is adjacent to an internal node contributing to $2k$ degree and the other node might be adjacent to an internal node or a leaf. Hence we are left with $2k$ degree that needs to be covered by the nodes which have an incoming edge to them.

We also know that each node has only one incoming edge except the root. Thus, $k-1+N$ nodes have an incoming edge to them. Thus,

$$2k = k-1+N \implies k = N-1$$

Thus, we proved that there are $N-1$ internal nodes for a directed singly-rooted binary tree with $N$ leaves.

Remark: The above argument can be easily adapted for undirected version.