Total number paths between two nodes in a complete graph

I assume $P$ is the number of nodes.

The actual number of paths between the two nodes which have $k$ extra vertices is $\frac{(P-2)!}{(P-2-k)!}$, for $0\leq k\leq P-2$. This is because you can choose $k$ other nodes out of the remaining $P-2$ in $\frac{(P-2)!}{(P-2-k)!k!}$ ways, and then you can put those $k$ nodes in any order in the path.

So the total number of paths is given by adding together these values for all possible $k$, i.e. $$\sum_{k=0}^{P-2}\frac{(P-2)!}{(P-2-k)!}=(P-2)!\sum_{j=0}^{P-2}\frac{1}{j!},$$ where $j=P-2-k$. Now $\sum_{j=0}^{\infty}\frac{1}{j!}=e$, so $$(P-2)!\sum_{j=0}^{P-2}\frac{1}{j!}\approx(P-2)!e.$$ This will always be an overestimate, but it will be an overestimate by $(P-2)!\sum_{j=P-1}^{\infty}\frac1{j!}\approx\frac1{P-1}$, and in fact the error will always be less than $1$. So just rounding down to the next integer will give the right answer.

The number of paths with $k$ edges ($1\le k\le P-1)$ between two distinct vertices in the complete graph $K_P$ is $$(P-2)(P-3)\cdots(P-k)=\frac{(P-2)!}{(P-k-1)!}$$ so the total number is $$(P-2)!\left(\frac1{(P-2)!}+\frac1{(P-3)!}+\cdots +\frac{1}{1!}+1\right).$$ The bracket is very close to $e$.

Firstly, we should be precise: the formula $\lfloor (P-2)! e \rfloor$ holds only for $\boldsymbol{P \ge 3}$. This, an addition to the floor operation, suggests that the formula's correctness relies on some approximation.

As Especially Lime's answer explains, the actual number of paths is $$ \sum_{i=0}^{P-2} \frac{(P-2)!}{i!}. $$ Now, to prove that for some integer $x$ and real number $y$, $x = \lfloor y \rfloor$, one shows that $x \le y < x + 1$. So what we formally need to show is $$ \sum_{i=0}^{P-2} \frac{(P-2)!}{i!} \le (P-2)!e < \sum_{i=0}^{P-2} \frac{(P-2)!}{i!} + 1. $$ Expand $e$ as $\sum_{i=0}^\infty \frac{1}{i!}$ and we get: $$ \sum_{i=0}^{P-2} \frac{(P-2)!}{i!} \le \sum_{i=0}^\infty \frac{(P-2)!}{i!} < \sum_{i=0}^{P-2} \frac{(P-2)!}{i!} + 1. $$ Subtracting terms $0$ to $(P-2)$ from all three terms of the inequality, we need to show that $$ 0 \le \sum_{i=P-1}^\infty \frac{(P-2)!}{i!} < 1. $$ The first part of the inequality is true because all terms are nonnegative, i.e. $(P-2)! \ge 0$. For the second part of the inequality, we have \begin{align*} \sum_{i=P-1}^\infty \frac{(P-2)!}{i!} &= \frac{1}{(P-1)} + \frac{1}{P(P-1)} + \frac{1}{(P+1)P(P-1)} + \cdots \\ &< \frac{1}{P-1} + \frac{1}{P(P-1)} + \frac{1}{(P+1)P} + \frac{1}{(P+2)(P-1)} + \cdots \\ &= \frac{1}{P-1} + \left( \frac{1}{P-1} - \frac{1}{P} \right) + \left( \frac{1}{P} - \frac{1}{P+1} \right) + \cdots \\ &= \frac{2}{P-1} \qquad \text{(telescoping)} \\ &\le 1 \qquad \qquad \text{(since } P \ge 3 \text{)}. \end{align*} This completes the proof.