Upper bound on size of $r$-balls about a vertex

Question

In the proof of Theorem 2.7 of Nica's Brief Introduction to Spectral Graph Theory, it is stated:

Let $u$ be a fixed vertex, and let us consider successive spheres around $u$. For each radius $r\geq1$, we can bound the size of an $r$-ball as

$$|B_r(u)| \leq 1+d+d(d-1) + \dots + d(d-1)^{r-1} < d(d-1)^r,$$

where $u$ is a vertex on a simple undirected graph with maximal degree $d \geq 3$.

I would like to verify this inequality, but consider the following ternary tree graph (please ignore the arrows and labels):

Here we have $d =3$. Let $u$ be the vertex labeled "$30$" in the given example. It seems that $\vert B_1(u)\vert =1 + 3 = 4$, $|B_2(u)| = 1 + 3 + 3^2= 13$. But according to the left-hand inequality above, the graph should satisfy the bound $|B_2(u)| \leq 1 + 3 + 3 \cdot 2 = 10$.

What am I missing?

Answer 1

Your inequality is correct.

The issue is that in the example you give, $d$ is equal to four, not three! The arrows in your example are misleading, since this inequality holds for undirected graphs only.

The $(d-1)$ terms of the inequality come from the fact that each vertex at distance $i$ must have some neighbour 'behind' it at distance $i-1$, and can thus only have at most $(d-1)$ neighbours 'ahead' of it at distance $i+1$. In your example, the vertices 5, 11 and 63 have one neighbour behind them, and three ahead, for a total of $d=4$.