Note that given is Complete graph ===> there is a edge between every pair of vertices.
we have n vertices, let name them as V_{1},V_{2},...V_{n}.
We want the paths between V_{1} and V_{n}.
there are remaining, n-2 elements, i.e., V_{2},V_{3},....V_{n-1} . ===> let the Set S = { remaining elements } ===> |S| = n-2.
what is the Power Set of this elements ===> size of power Set of S = 2^{n-2}.
in the power set, each set is lead to unique path ( labels are in the path are strictly increasing order ) between V_{1} and V_{n}.
∴ No.of Simple paths between V_{1} and V_{n} Such that the labels in the path are strictly increasing order = 2^{n-2}.
ex:-
let take K_{5}..... name the labels as V_{1},V_{2},V_{3},V_{4},V_{5}.
We want the simple paths between V_{1} and V_{5}.
remaining vertices are {V_{2},V_{3},V_{4}}, then the power set is contains the following set
1) ∅ ====> the path which we required is V_{1} --- V_{5}.
2) { V_{2} } ====> the path which we required is V_{1} --- V_{2} --- V_{5}.
3) { V_{3} } ====> the path which we required is V_{1} --- V_{3} --- V_{5}.
4) { V_{4} } ====> the path which we required is V_{1} --- V_{4} --- V_{5}.
5) { V_{2},V_{3} } ====> the path which we required is V_{1} --- V_{2} --- V_{3} --- V_{5}.
6) { V_{2},V_{4} } ====> the path which we required is V_{1} --- V_{2} --- V_{4} --- V_{5}.
7) { V_{3},V_{4} } ====> the path which we required is V_{1} --- V_{3} --- V_{4} --- V_{5}.
8) { V_{2},V_{3},V_{4} } ====> the path which we required is V_{1} --- V_{2} --- V_{3} --- V_{4} --- V_{5}.
Now i am interested in that,what the formula if in the question the restriction " labels are in the path are strictly increasing order " removed ?
the power set contains = 2^{n-2}. sets
we can partition them as
$\binom{n-2}{0} + \binom{n-2}{1} + \binom{n-2}{2} + ...+ \binom{n-2}{n-2}$ = 2^{n-2}.
$\binom{n-2}{0}$ ===> lead to 1 permutation paths
$\binom{n-2}{1}$ ===> lead to 1 permutation paths
$\binom{n-2}{2}$ ===> lead to 2 permutation paths
............
$\binom{n-2}{n-2}$ ===> lead to (n-2)! permutation paths
∴ No.of Simple paths between V_{1} and V_{n} = $\binom{n-2}{0} * 1! + \binom{n-2}{1} * 1! + \binom{n-2}{2} * 2! + ...+ \binom{n-2}{n-2} * (n-2)! $.