Number of inner nodes in relation to the leaf number N 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,

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.
