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$

  • $\begingroup$ $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. $\endgroup$ – Ali Sep 1 '14 at 6:35
  • $\begingroup$ Your question already contains what you claim to be an answer so I'm not sure what you're asking. $\endgroup$ – David Richerby Sep 1 '14 at 7:28
  • $\begingroup$ I'm Asking : How many simple paths between two vertices in n-clique? $\endgroup$ – Ali Sep 1 '14 at 8:58
  • 1
    $\begingroup$ 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? $\endgroup$ – Raphael Sep 1 '14 at 10:59
  • $\begingroup$ I won't to compute the complexity of my algorithm,so i need the size of simple paths between two vertices. $\endgroup$ – Ali Sep 1 '14 at 13:51



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


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

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

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