I am struggling to understand graph theory induction questions. I understand the basics of induction as well as graph theory, however, when working on these types of problems I seem to struggle to find a good approach for them. I would like for someone to help solve this problem and walk through their method of working on problems such as this. The question is as follows:
Let $T = (V, E)$ be a rooted tree with the property that every internal vertex has exactly 2 children. If there are $k$ internal vertices, prove by induction that $|V | = 2k + 1$.
Any help is appreciated.
Perform induction on $k$. The bases $k=0$ and $k=1$ are easy. Suppose now that $T$ is a rooted tree with $k>1$ internal vertices.
Having at least $k\ge 2$ vertices, the tree has at least one leaf, so let $v$ be a leaf. Note that $v$ can't be the root, so it has a parent. If $u$ is a parent of $v$, then $u$ must have another child $w$. Removing $v$ and $w$ from $T$ yields another rooted tree with $k-1$ internal vertices ($u$ is now no longer an internal vertex). This new tree must have $2(k-1)+1=2k-1$ vertices by our induction hypothesis. Therefore, $T$ must have $2k-1+2=2k+1$ vertices (since we are adding $v$ and $w$ back).
Here is another solution. Let $n$ be the number of vertices. Then the tree has $n-k$ leaves. The root has degree $2$. Each non-root internal vertex has degree $3$ (for it has one edge joining it to its parent, and two edges joining it to its two children), so the degree sum is $$2+3(k-1)+(n-k)=n+2k-1.$$ But the tree must have $n-1$ edges, so the degree sum should be $2(n-1)$. That is, $$n+2k-1=2(n-1)\implies n=2k+1.$$
Generalisation: A rooted tree with $k$ internal vertices in which each internal vertex has exactly $t$ children must have exactly $tk+1$ vertices. Even more generally if $T$ is a finite rooted tree such that for a non-negative integer $n$ there are $k_n$ vertices with exactly $n$ children, then $T$ has $\sum_{n=0}^\infty nk_n+1$ vertices.