Fix an integer $d>1$. Let $G$ be a tree with $n$ vertices, and every vertex can have either degree $1$ or $d$. Find the number of degree $1$ vertices in terms of $d$ and $n$.
I've been working on this problem and I feel like I almost have the answer. I worked out that if $d=2$, the graph will just be a line with vertices and $2$ leaves, so there will be $2$ vertices with $\deg(1)$, no matter how many vertices there actually are. If $d=3$, $n$ starts to matter.
Using the fact that the sum of all the $\deg(v)$ of a graph is $2|E|$ and that in a tree $|E|=|V|-1$ I worked out that the sum of $\deg(v)=2n-1$, and that this sum mod $d$ will be the amount of degree $1$ vertices. ( Since $d+d+d+\dots+1+1+1+1$ mod $d$ will be the sum of the $1$'s unless the sum is greater than $d$, then it will wrap around). I'm having a hard time putting this all together into a simple equation. I don't want just the solution, I want to understand how to find the equation as well.
Best Answer
Let $n_1$ be the number of degree $1$ vertices, and $n_d$ the number of degree $d$ vertices.
Then (the first two lines are the facts as you have already noted): $$ |E| = \frac12 \sum \mbox{ deg } v_i = \frac12 ( n_1 + d n_d ) \\ |E| = |v| - 1 = (n_1 + n_d) -1 \\ \frac12 ( n_1 + d n_d ) = (n_1 + n_d) -1 \\ n_1 + n_d = n \implies n_d = n - n_1\\ \frac12 ( n_1 + d (n-n_1) ) = n - 1 \\ n_1 + d (n-n_1) = 2(n - 1) \\ n_1(1-d) + nd = 2n - 2 \\ n_1 = \frac{(2-d) n - 2}{1-d} = n + \frac{n-2}{d-1} $$