A graph $G$ of radius at most $k$ and maximum degree at most $d$ has no more than $1 + kd^k$ vertices

Question

Proposition: A graph $G$ of radius at most $k$ and maximum degree at most $d$ has no more than $1 + kd^k$ vertices.

Assuming that $d > 2$ and $k > 3$, improve the bound in above proposition to $d^k$.

The above question is from exercise problem in Diestel's book. How can we formally prove this?

Answer 1

Let $G(V,E)$ be a simple graph with radius at most $k$ and maximum degree at most $d$. Fix a center $u\in V$ of $G$ (i.e., any path from $u$ to another vertex of $G$ is of length at most the radius of the graph). A vertex $v\in V$ is of level $l\in\{0,1,2,\ldots,k\}$ if the shortest path from $u$ to $v$ is of length $l$. Write $N_l$ for the number of vertices of level $l$.

First, $N_0=1$. Thus, $N_1\leq d$. We can easily seen that $$N_{l+1}\leq (d-1)\,N_l\text{ for }l=1,2,\ldots,k-1\,,$$ because a vertex of level $l+1$ must be joined by an edge to a vertex of level $l$, and each vertex of level $l$ can is adjacent to at most $d-1$ vertices of level $l+1$, having one edge connected to a vertex of level $l-1$. That is, $$N_{l}\leq d\,(d-1)^{l-1}\text{ for }l=1,2,3,\ldots,k\,.$$ If $d>2$, then $$\begin{align} |V|&= \sum_{l=0}^k\,N_l\leq 1+d\,\sum_{l=1}^k\,(d-1)^{l-1}\leq 1+kd(d-1)^{k-1}\leq 1+kd^k\,. \end{align}$$ If $d=2$, then obviously, $N_l\leq 2$ for all $l=1,2,\ldots,k$, whence $$|V|\leq 1+2k\leq 1+kd^k\,.$$ If $d=1$, then the graph consist of at most $2$ vertices, so $$|V|\leq 2\leq 1+kd^k\,,$$ as $k\geq 1$.

The inequalities $$|V|\leq 1+d\,\sum_{l=1}^k\,(d-1)^{l-1}=\left\{ \begin{array}{ll} 1+d\left(\frac{(d-1)^k-1}{(d-1)-1}\right)\,,&\text{ for }d\neq 2\,,\\ 1+2k\,,&\text{ for }d=2\,,\end{array}\right.$$ are sharp, and stronger than the original inequality $|V|\leq 1+kd^k$. An example in each case should be easy to find. We can also show that $|V|< d^k$ for $d\geq 2$ and $k\geq 3$. The case $d=2$ is trivial. For $d>2$, we note that $$\begin{align}(d-2)\,\left(\frac{d^k-1}{d}\right)&> (d-2)\,\left(d^{k-1}-1 \right) = d^2(d-2)\,d^{k-3}-(d-2) \\ &> \left((d-1)^3+d^2\right)\,d^{k-3}-(d-2)\geq (d-1)^3\,d^{k-3}+d^2-(d-2) \\ &>(d-1)^3\,d^{k-3}-1\geq (d-1)^k-1\,,\end{align}$$ whence $$|V|\leq 1+d\,\left(\frac{(d-1)^k-1}{d-2}\right)<d^k\,.$$

Answer 2

Let $v$ be a central vertex of the graph. This has at most $d$ neighbors. Each neighbor has at most $(d-1)$ other neighbors, for at most $d(d-1)$ total new vertices. Each of these neighbors has at most $(d-1)$ other neighbors, for $(d-1)^2d$ total new vertices. Continuing in this fashion, you get the summation $$ 1+ d + d(d-1) + d(d-1)^2 +d(d-1)^3+\dots = 1+\sum_{i=0}^{k-1}d(d-1)^i $$ Note that the summation stops at $k$, because the distance from $v$ to any other vertex is at most $k$.