What is the maximum number of simple paths between two vertices $s$ and $t$ in a graph $G=(V,E)$? I am looking for an upper bound for this problem.
What I have done? I assumed that $s$ and $t$ must be in a clique of size $n$. Let ${\cal P}_{st}$ be the set of all paths between $s$ and $t$, which we are interested in $|{\cal P}_{st}|$. Let ${\cal P}^{(k)}_{st}$ be the set of simple paths with length $k$ between $s$ and $t$ in $G$. Thus,
$$|{\cal P}_{st}| = \sum_{1 \leq k \leq n-1}{|{\cal P}^{k)}_{st}|} = \sum_{1 \leq k \leq n-1}{\frac{(n-2)!}{(n-1-k)!}} = T(n-2)$$
and I know that $T(n)=nT(n-1)+1$. Is there a way to calcualte the final results in terms of $n$?
Your sum can be written as $$(n-2)!\Bigl(1+\frac1{1!}+\frac1{2!}+\cdots+\frac1{(n-2)!}\Bigr)\ ,$$ which is less than and very close to $$(n-2)!\,e\ .$$
Edit in response to question. The relative error is $$\frac{e-{\displaystyle \Bigl(1+\frac1{1!}+\frac1{2!}+\cdots+\frac1{(n-2)!}\Bigr)}}{{\displaystyle \Bigl(1+\frac1{1!}+\frac1{2!}+\cdots+\frac1{(n-2)!}\Bigr)}}$$ which if $n$ is large is approximately $$\frac1{(n-1)!\,e}\ .$$