5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Relative0
    May 13 '13 at 9:28
  • 1
    $\begingroup$ @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. $\endgroup$
    – EuYu
    May 13 '13 at 9:32
  • $\begingroup$ 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? $\endgroup$
    – Relative0
    May 14 '13 at 5:54
  • $\begingroup$ @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. $\endgroup$
    – EuYu
    May 14 '13 at 6:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.