To answer the question number of paths of length 4 between vertices 1 and 2 in the complete graph $K_n$.
I think there are 3!C(n,3) paths?
because in a complete graph, all vertices are connected, that implies you can travel among any of them without any problem.
Here, a length 4 path has 5 vertices, so it implies n choose 5, however, it requires that all these paths are between vertices 1 and 2, so, 2 of the 5 points are fixed in this case.
Therefore, it is n choose 3, also, then each of the subset of these 3 vertices can permute and form different graph.
So, my conclusion is 3!C(n,3). did I miss anything?
also, do I need to multiple my answer if it is correct? since a path can go both ways.
Best Answer
Your logic is correct except that one would choose three vertices from among $n-2$ available vertices (you cannot revisit vertex $1$ and $2$), giving $$ 3! C(n-2,3) = (n-2)(n-3)(n-4) $$ possible paths.
You could interpret that solution in another way. Begin at vertex 1 and choose the next vertex in your path. There are $n-2$ choices available (any vertex except 1 or 2). Now choose the next vertex in your path from the remaining $n-3$ vertices, and the next from the remaining $n-4$ vertices. Now you must finish your path at vertex 2, giving you no freedom to choose. Multiplying the number of options at each step gives a total of $(n-2)(n-3)(n-4)$ paths.