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$


closed as unclear what you're asking by lPlant, FrankW, Juho, David Richerby, Wandering Logic Sep 6 '14 at 3:52

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.