# 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$$

• Holy Cow! I was way off! Thanks EuYu. I don't think the instructor ever even mentioned that there was a Gamma function involved in anything in the class - so it didn't even come to mind, I will have to look it up. I appreciate your time, thanks again. May 13 '13 at 9:28
• @user1922184 The incomplete gamma is not truly necessary. It just gives a tidy way for expressing the formula. The sum given in the first line is sufficient if you're unfamiliar with the gamma.
– EuYu
May 13 '13 at 9:32
• Thanks again EuYu. I am wondering two things. First, as you said "Your path can be anywhere between length 3 and length n", what about those paths that are u -> v -> w as those have length 2, or is since there is only 1 of those (directly from u to v to w) that is just one choice? Also, for (k-2)! choices of re-arrangements is that because there is whatever path was used to come to v as well as a single path directly from v to w which gives us k-2 other paths? May 14 '13 at 5:54
• @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