[Math] Graph theory: Finding the number of different paths through a vertex on a complete graph

graph theory

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

Best Answer

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

Related Solutions

[Math] Total number of linear paths from any vertex to any other in an undirected graph

With up to 50 vertices, the number of paths could be enormous: in a complete graph of 50 vertices (i.e. every vertex joined to every other vertex) there would be $41337038439638629286248290504650886651492243224669378150412649225$ of them: that's $\sum_{k=2}^{50} \frac{50!}{2 (50-k)!}$. Hopefully your graphs will be sparse enough that the number will be much more reasonable. You might try a recursive approach: if $P(i,S)$ is the number of paths starting with vertex $i$ and with all other vertices in set $S$, and $N(i)$ is the set of vertices $j$ such that $(i,j)$ is an edge, then $P(i,S) = \sum_{j \in N(i) \cap S} (1 + P(j,S \backslash \{j\}))$. Note that this will overcount the paths by a factor of 2.

[Math] Number of Hamiltonian Paths on a (in)complete graph

This looks a lot like the way you determine the chromatic polynomial, but in a some sense "reversed": you know the values of your most "complicated" graphs instead of iterating until you have reached the simplest ones.

Consider one edge $e$, then the number of hamiltonian cycles in $G$ equals the number of cycles in $G-e$ (those that do NOT use the edge) plus the number of cycles in $G/e$ (those that DO use the edge).

This can be transformed into a recursive algorithm: you know the values for the complete graphs, and all other intermediate values you require are the result of removing a smaller list of edges from a smaller complete graph.

However this will not perform at all on anything but the smallest examples and it certainly will not give you anything like a closed formula for the number of hamiltonian cycles. I am not at all sure if this is an acceptable solution.

EDITED AFTER REQUEST FOR DETAILS:

Consider next pseudocode.

int function h(int n, List l)
{
  if (l is empty) { return number of hamilton cycles in K_n }
  create new list lNew;
  return h(n, l minus last element) - h(n - 1, lNew);
}

This function $h$ calculates the number of hamiltonian cycles in $K_n$ when the edges of the list $l$ are missing. You use the recurrence $h(G-e)=h(G)-h(G/e)$, so you repeatedly put one edge back into the graph until you have put back everything. You have to decide on how to represent the edges on the list. One option is to represent each edge on $l$ simply as a pair of numbers in the range $1..n$. The only tricky part is the creation of the list $lNew$. You cannot just copy its elements from the list $l$, since they refer to edges of a $K_{n-1}$ after the recursion, so depending on the edge you are removing you need to manipulate the list elements.

I have no clue how this will perform with the numbers you mention. The most important thing will be that the list of edges is not too long, since that will determine the depth of the recursion. Be sure to use some kind of 'big integer' arithmetic or find other ways to avoid large numbers.

Best Answer

Related Solutions

[Math] Total number of linear paths from any vertex to any other in an undirected graph

[Math] Number of Hamiltonian Paths on a (in)complete graph

Related Question