2
$\begingroup$

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,

2 Answers 2

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

  • 1
    I have to say that if this were presented to me I'd give it an 'Incomplete' - you don't say anything about what your inductive argument _is_, just give the formula for n and for n+1 and say 'the k+1 follows from the k step' but you've said nothing about how this relates to the problem at all. Can you flesh that argument out at all?2011-02-21
3

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.

  • 0
    I did it myself2011-02-20