# Graph theory: Finding the number of different paths through a vertex on a complete graph

If G is a complete graph on n vertices and u,v,w are three distinct vertices in the vertex set of G, then how many different paths are there from u to v passing through w?

For 3 vertices it is simple, each vertex has degree 2, one of the edges leading directly v - so there is only 1 path.

For 4 vertices, it looks as if there are 3 distinct paths going through any fixed vertex w.

For 5 vertices it is becoming tricky and since there are 3 edges not going directly to v, but they can go to each other... well I have counted at least 8 distinct paths so far and am thinking maybe that is correct - that somehow maybe for 3 vertices, there is one edge not going directly to v, and (inventing a relation) 1^2 - 1 = 1 which is true. For 4 vertices it would be 2 distinct edges not going to v so 2^2 - 1 = 3 which works. Then for 5 vertices, the 3 distinct edges not going to v would give me 3^2 - 1 = 8.

So in general I could come up with a formula of $$(n-2)^{2} -1.$$ But this is a shot in the dark and I have no idea. Any thoughts?

Thanks,

Brian

-

Let $p_n$ denote the total number of paths between $u$ and $v$ through some $w$. Your path can have anywhere between $3$ and $n$ vertices. If your path has $k$ vertices, then there are $k-3$ choices of intermediate vertices from the $n-3$ free vertices together with $(k-2)!$ choices of rearrangements. Therefore in total we have $$p_n=\sum_{k=3}^n\binom{n-3}{k-3}(k-2)! = \sum_{k=3}^n\frac{(n-3)!}{(n-k)!}(k-2)$$ This is essentially the formula, but there is a "closed form" in terms of the incomplete gamma function if you want.
We rewrite the sum with $\ell = n-k$ as $$p_n=(n-3)!\sum_{\ell=0}^{n-3}\frac{n-\ell-2}{\ell!}=(n-2)!\sum_{\ell=0}^{n-3}\frac{1}{\ell!}-(n-3)!\sum_{\ell=0}^{n-4}\frac{1}{\ell!}$$ Each of the summands can be expressed in terms of the incomplete gamma function, namely $$k!\sum_{\ell=0}^{k-1}\frac{1}{\ell!} = ek\Gamma(k,\ 1)=ek(k-1)\Gamma(k-1,\ 1) + k$$ where $e$ is the base of the natural logarithm and $\Gamma(k,\ 1)$ is the incomplete gamma function. Using the above, we can simplify as \begin{align}p_n &= e(n-2)\Gamma(n-2,\ 1)-e(n-3)\Gamma(n-3,\ 1) \\&=e(n-2)(n-3)\Gamma(n-3,\ 1)-e(n-3)\Gamma(n-3,\ 1) + n-2 \\&=e(n-3)^2\Gamma(n-3,\ 1)+n-2\end{align}
The sequence begins from $n=3$ as $$1,\ 3,\ 11,\ 49,\ 261,\ 1631,\ \cdots$$
@user1922184 Ah, I was referring to the length as in the number of vertices. I probably should have mentioned that. The $(k-2)!$ rearrangements comes from permuting the central vertices of the path. If there are $k$ vertices in your path then there are $k-2$ central vertices (excluding the endpoints $u$ and $v$). These $k-2$ central vertices can be permuted anyway you want, giving $(k-2)!$ rearrangements. – EuYu May 14 '13 at 6:14