Let $ G $ be a tree with 14 vertices of degree 1, and the degree of each nonterminal vertex is 4 or 5. Find the number of vertices of degree 4 and degree 5.
My attempt, summarized, is the following: Let $ x $ be the number of vertices of degree 4, let $ y $ be the number of vertices of degree 5. Note that there are $ x + y + 14 $ vertices ($ x + y + 13 $ edges, since $ G $ is a tree), then $ 4x + 5y + 1 (14) = 2x + 2y + 26 $ applying handshaking lemma (the sum over all vertices of the degrees is two times the number of edges). But the solution to this is $x = – \frac{3}{2} y + 6$. I don't know if it's okay or what I'm doing wrong.
Best Answer
You were on the right track.
From $$4x + 5y + 14 = 2x + 2y + 26$$ we get $$ 2x+3y=12 $$ It follows that $y$ is even and at most $4$, hence $$ (x,y)\in\bigl\{(0,4),\;(3,2),\;(6,0)\bigr\} $$ As we'll show, all $3$ of these potential pairs $(x,y)$ are, in fsct, possible.
The image below shows an example with $(x,y)=(0,4)$.
And the image below shows an example with $(x,y)=(3,2)$.
Finally, the image below shows an example with $(x,y)=(6,0)$.
Thus, as claimed, each of the pairs $$ (x,y)=(0,4),\qquad(x,y)=(3,2),\qquad(x,y)=(6,0) $$ can actually be realized.