Let $T$ be a nonempty 2-3 tree, so that it includes at least one node. Prove that if $T$ represents a subset $S\subseteq E$ such that $|S|= n\in \Bbb N$, then $T$ has at most $n-1$ internal nodes.
I figure you have to use induction, but I get stuck at the proof itself. Here's what I have so far:
Basis: When $n = 1$, $|S| = 1$, so $T$ is a nonempty tree with size $1$. Since it has size one, there is only one node, which is the root, which in this case is also a leaf, and cannot be an internal node. Then, $n – 1 = 1 – 1 = 0$ internal nodes, which proves that the basis holds.
Inductive hypothesis: Suppose that every subset $S\subseteq E$ with size $n$, represented by $T$, has at most $n – 1$ internal nodes.
Any help is appreciated!