How many vertices are of degree 1?

Question

Given $T(n,m)$ which contains only vertices of degree 1 and 3. How many vertices are of degree 1? Is it similar to compute in thi link? How many vertices of degree 1 in a tree? Thank you.

Answer 1

As a base case, the Claw graph is a minimal example, and it has three $\deg 1$ vertices (it is an example of $T(4,3)$). Each time we add a new interior vertex from here, we must increase the count of $\deg 1$ vertices by 1, but the total vertex count goes up by 2, hence we see that a tree of this type must have exactly $2k$ total vertices for some $k>1$, and $\frac{n}{2}+1$ degree 1 vertices.

Answer 2

Taking the first answer in the linked question here as a basis, you can imagine your graph describing a single elimination tournament where the final match is instead a 3 person free-for-all instead of the usual one-on-one matches.

For $n$ players, to eliminate $n-3$ of them there will be $n-3$ games played one-on-one, and then one more game for the final match free-for-all.

Such a graph will have $2n-2$ vertices. One can argue via contrapositive that if it had a different number of vertices it would necessarily have a different number of leaves.

Rewording such that the total number of vertices is $n$ then, we have $\frac{n+2}{2}$ vertices of degree one.

(note: having an odd number of vertices total is not allowed by the handshaking lemma)