A tree on n vertices where every vertex has degree 1 or 4. Prove that n ≡ 2 (mod 3)

Question

Let T be a tree tree on n vertices where every vertex has degree 1 or 4. Prove that n ≡ 2 (mod 3)

Answer 1

The sum of the degrees of all vertices is congruent to $n$ mod $3$ (since it is a sum of $n$ terms that are all congruent to $1$ mod 3) and is also equal to $2n-2$ since the tree has $n-1$ edges. Thus $$2n-2\equiv n\pmod{3}$$ so $$n\equiv 2\pmod{3}$$

Answer 2

HINT: If every vertex has degree $1$, the tree is $K_2$. Otherwise, pick a vertex $v$ of degree $4$, and split it into $4$ vertices, one adjacent to each edge of the original tree that was adjacent to $v$. You now have a forest of four trees, each of which is smaller than the original tree, and each of which has only vertices of degrees $1$ and $4$. Now apply the natural induction hypothesis.