I am taking an introductory proofs course and I find it difficult to formulate a proof even though it may be something trivial. In essence I find it difficult to determine whether I should use a direct proof, a proof by contraction or even induction. I hope you guys can help me out.
Let T be a tree on n vertices where every vertex has a degree 1 or 4. Prove n $\equiv$ 2 (mod 3).
I want to utilize a direct proof. I want to show that to start off, the root of the tree must be connected to one other vertex with one edge. This means we would have 2 vertices and one edge between them. From that point on, anytime we need to 'grow' the tree, the number of vertices we have to add is 3. We cannot add any other number since it would mean having a degree that is not 1 or 4. By starting of with 2 vertices, and adding 3 every time we get a number that is congruent to 2 (mod 3). Am I on the right path here?
Let $x$ be the number of vertices of degree $4$ and $n-x$ be the number of vertices of degree $1$. Since $T$ is a tree of order $n$ we know that it has size $n-1$ and by the First Theorem of Graph Theory we have $4x+(n-x)=2(n-1)$ and so $3x=n-2$ and it follows that $n\equiv 2 \pmod 3$.