I've recently stumbled across a problem that states the following:
Given G a connected graph, $D$ the maximum shortest distance between two vertices in in the graph and $\Delta > 2$ the maximum degree a vertex has then prove that the minimum number of vertices in $G$ is
$$\frac{\Delta (\Delta -1)^D-2}{\Delta -2}$$
I think I've managed to solve it but I get a lower upper bound than the one above so I think I might have made a mistake.
The whole idea of my proof is around generating trees. I've used these because they have the same ammount of vertices as the original graph and it's easier to find an upper bound for trees than regular graphs.
First, given a diameter $D$ and maximum degree $\Delta$, the largest (with the most vertices) tree following those properties would be the tree with hight $h=D$ and where the level of all the leafs is $D$. On top of that, every vertex on the tree has to have $(\Delta-1)$ descendants.
I think that if there's any mistakes, they have to be on the reasoning behind this last paragraph as from here the reasoning is straightforward.
Now, in order to determine this "worst case scenario" tree, I've only needed to get the expression for the leaves of a tree like that and from there for the vertices as a function of the leaves.
$$f=(\Delta -1)^D$$
Is the number of leaves in a tree of these characteristics and
$$n=\frac{mf-1}{m-1}$$
Is the number of vertices.
From here, I get the expression
$$n=\frac{(\Delta -1)^{D+1}-1}{\Delta -2}< \frac{\Delta(\Delta -1)^D-2}{\Delta -2}$$
Where the last inequality holds as long as $\Delta >2$.
Now as the proposed generating tree is the case with the most vertices, the following inequalities give the solution to the problem:
$$|V(G)|=\leq\frac{(\Delta -1)^{D+1}-1}{\Delta -2}< \frac{\Delta(\Delta -1)^D-2}{\Delta -2}$$
However, due to how similar both expressions are and how the problem asks to prove that the particular expression is a minimum, I belive I might have made a mistake in the reasoning even though I can't find where.
I'd apreciate if anyone could point the mistake to me or give me a hint on how to face the proof.
Thanks in advance
First, you wrote that the problem is to find the minimum number of vertices in such a graph, but clearly you are thinking about the maximum number (the bounds also suggests that it should be the maximum).
Second, your idea of looking at trees is good, but the number of leaves in the tree you are looking for is actually $\Delta(\Delta-1)^{D-1}$. This is because the root vertex can actually have $\Delta$ descendants instead of $\Delta-1$. If you calculate from this the number of vertices in the tree, you will get the claimed bound.
EDIT: Here's the calculation. Adding the maximum number of vertices on each "layer", you get \begin{align*} n &= 1 + \Delta + \Delta(\Delta-1) + \ldots + \Delta(\Delta-1)^{D-1} \\ &= 1 + \Delta\left(1 + (\Delta-1) + \ldots + (\Delta-1)^{D-1}\right)= 1 + \Delta\left(\frac{(\Delta-1)^{D} - 1}{\Delta-2}\right) \\ &= \frac{\Delta-2}{\Delta-2} + \frac{\Delta(\Delta-1)^D - \Delta}{\Delta-2} = \frac{\Delta(\Delta-1)^D - 2}{\Delta-2}. \end{align*}
Third, you write that you were considering trees because it is easier to find upper bounds for them. This is true enough, but the statement is about any connected graph, and it is unclear how your solution rules out the possibility that there is a non-tree graph with more vertices. You need a better argument for why this works. The hint for this is that you are not really thinking about trees, but rather about graphs with $D$ "layers", and any graph of diameter $D$ can be looked at in this way.