# Count of all simple paths between two vertices in a Complete graph [closed]

A path is simple if no vertices are repeated. How many simple paths exist between two vertices in a complete graph?

One way is listing all simple paths using depth-first search. but I think it should be more simple to find the number of all simple paths between 2 nodes in a complete graph.

Here is the same problem but mine is for a complete graph: Algorithm that finds the number of simple paths from $$s$$ to $$t$$ in $$G$$

• $countOfAllpathInClique(n)=\sum_{k=2}^n \binom{n}{k} \frac{k!}{2} = \Omega(2^n)$ $countPathBetween2vertices=countOfAllpathInClique(n-2)+2*(n-1)-1$ because we can assume we have a (n-2)clique + 2 other vertices. so after we computed the all path of (n-2)clique we should add 2*(n-1) new edge and one of them is not new. I'm not sure about the correctness of this.
– Ali
Sep 1 '14 at 6:35
• Your question already contains what you claim to be an answer so I'm not sure what you're asking. Sep 1 '14 at 7:28
• I'm Asking : How many simple paths between two vertices in n-clique?
– Ali
Sep 1 '14 at 8:58
• How is this different from "how many s-t-paths are there in the complete graph"? Also, what have you tried and where did you get stuck?
– Raphael
Sep 1 '14 at 10:59
• I won't to compute the complexity of my algorithm,so i need the size of simple paths between two vertices.
– Ali
Sep 1 '14 at 13:51

$c(1)=0,$

$c(n)=(n-2)*c(n-1)+1$

suppose we have c(n-1) path in (n-1)-Complete Graph. when we add one more vertices, we add $(n-2)*c(n-1)$ new path and one for directed path.

the result is same as real:

1. 0
2. 1
3. 2
4. 5
5. 16
6. 65

===============================EDITED

$c(n)=\sum_{i=0}^{n-2} \frac{(n-2)!}{i!}=(n-2)!*\sum_{i=0}^{n-2}\frac{1}{i!}$

.

This shows that's about $(2\text{≈}3)*(n-2)!$

• This doesn't seem to answer the question. OK, you have a recurrence but what's the solution of that recurrence? Sep 1 '14 at 7:27
• Thanks for you comment, I added the real value of the recurrence function.
– Ali
Sep 1 '14 at 9:49