Problem $4$

Here is a recursive definition for a set of trees. The set of trees called TREES.

Base case: The tree shown below is in TREES

Recursive rule: If $T$ is in TREES, then a new element of TREES called $T^{\text{'}}$ can be constructed by taking two coples of $T,$ adding a new vertex $v$ and adding edges between $v$ and the roots of each copy of $T.$ The new vertex $v$ is the root of $T^{\text{'}}.$

Note that the definition of TREES is the same as the definition for perfect binary trees except that the tree consisting of a single vertex is not included in the set TREES.

$($a$)$ The degree of a vertex is the number of edges connected to that vertex Define $d(v)$ to be the degree of vertex $v.$

Let $T$ be a tree in TREES and let $r$ be the root of $T.$ Then

$d(r)=2$

For every vertex $vr,d(v)=1$ or $d(v)=3.$

Prove: For every vertex $vr,d(v)=1$ or $d(v)=3.$