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$,


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


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


2 Answers 2


Hint What is $x+y$ ?

From there you are done.

  • $\begingroup$ oh, right, I'm an idiot. Thank you. $\endgroup$ Sep 24, 2014 at 22:53
  • 2
    $\begingroup$ @DianeVanderwaif We all miss simple things from time to time. And from my experience, when we get stucked on a problem, we tend to look for complex things, and can easily miss the obvious... So I wouldn't use the word idiot here :) $\endgroup$
    – N. S.
    Sep 24, 2014 at 22:55
  • $\begingroup$ @Diane Vanderwaif. Where did you incorporate the $x+y$ in your computation? Thank you. $\endgroup$
    – Bayoy
    Mar 13, 2016 at 16:01
  • $\begingroup$ @ N.S. How to incorporate the $x+y$ in the computation? Thank you. $\endgroup$
    – Bayoy
    Mar 13, 2016 at 16:02
  • $\begingroup$ @Bayoy $x+y=n$ leads to a system of two equations which is very easy to solve.... $\endgroup$
    – N. S.
    Mar 14, 2016 at 2:21

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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .