A certain tree $T$ of order $n$ contains only vertices of degree $1$ and $3$. Show that $T$ contain $\frac{n-2}{2}$ vertices of degree $3$.

Question

A certain tree $T$ of order $n$ contains only vertices of degree $1$ and $3$. Show that $T$ contain $\frac{n-2}{2}$ vertices of degree $3$.

Here is what i got so far:

Since $T$ is a tree of order $n$, the size of $T$,

$$m=n-1$$

I also know that the sum of degree of all vertices in a graph is double the size. Since $T$ contain only vertices of degree $1$ and $3$. Let $x,y$ be number of vertices of degree $1$ and $3$ respectively, we have

$$x+3y=2(n-1)$$

From here, I don't know how to get $y=\frac{n-2}{2}$

Answer 1

Hint What is $x+y$ ?

From there you are done.

Answer 2

Here is an answer that uses generating functions and Lagrange inversion, to verify that it produces a correct result, to present the method and to motivate additional exploration.

Note that this type of tree can be obtained by taking three rooted ordered proper binary trees and attaching them to a root node. (In fact every node of degree three in the tree can play this role.)

Now the species $\mathcal{T}$ of binary trees with nodes of degree three marked has equation $$\mathcal{T} = \mathcal{Z} + \mathcal{U}\mathcal{Z} \mathcal{T}^2.$$

This gives the functional equation for the generating function $T(z)$ $$T(z) = z + uz T(z)^2.$$

We extract coefficients from this with Lagrange Inversion starting from $$[z^n] T(z) = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) \; dz.$$

Put $T(z)=w$ so that $$z = \frac{w}{1+uw^2}$$ and $$dz = \left(\frac{1}{1+uw^2} - \frac{w\times 2uw}{(1+uw^2)^2} \right)\; dw$$ which gives for the integral $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+uw^2)^{n+1}}{w^{n+1}} w \left(\frac{1}{1+uw^2} - \frac{2uw^2}{(1+uw^2)^2}\right)\; dw.$$

We process the two components in turn. The first is $$\frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{(1+uw^2)^n}{w^n} \; dw$$ and the second $$\frac{1}{2\pi i} \int_{|w|=\epsilon} 2u \times \frac{(1+uw^2)^{n-1}}{w^{n-2}} \; dw.$$

The first gives for $n$ odd the contribution $$u^{(n-1)/2} {n\choose (n-1)/2}$$ and the second one also for $n$ odd $$2u \times u^{(n-3)/2} {n-1\choose (n-3)/2}.$$

This yields $$u^{(n-1)/2} \times\left({n\choose (n-1)/2} - 2{n-1\choose (n-3)/2} \right).$$ which simplifies to $$u^{(n-1)/2} \times \frac{1}{(n+1)/2} {n-1\choose (n-1)/2}$$ where we have encountered the Catalan numbers which are OEIS A000108.

This shows that every such binary tree has $(n-1)/2$ nodes of degree three. If we take three such trees on $n_1, n_2$ and $n_3$ nodes and attach them to a root node the resulting tree has $n_1+n_2+n_3+1$ nodes and $(n_1+n_2+n_3-3)/2+1$ nodes of degree three including the root.

But we have $$\frac{(n_1+n_2+n_3+1)-2}{2} = \frac{n_1+n_2+n_3-1}{2} = \frac{n_1+n_2+n_3-3}{2}+1$$ and the claim holds.

The point here is of course that this very same method can be used to prove much more difficult results including producing the distribution of the parameter marked by $u$ when it is not constant in the object space corresponding to a fixed value of the main variable.