Number of simple path from $u$ to $v$

Question

Question

A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let $G$ be a complete graph on $10$ vertices. Let $u, v,w$ be three distinct vertices in $G$.How many simple paths are there from $u$ to $v$ going through $w$?

My Approach

I first selected $u,v$ from $10$ vertices by $$\binom{10}{2}$$ then $w$ from remianing $8$ by $$\binom{8}{1}$$

So my possible number of simple path from $u$ to $v$ = $$\binom{10}{2}*\binom{8}{1}*7!$$

But answer seems wrong.

Where am i wrong? Please help me out

Answer 1

According to the text we may assume that nodes $u,v,w$ are given, fixed and we have to count the number of simple paths from $u$ to $v$ via $w$.

We consider simple paths according to their length $l$, which is the number of edges of the path.

The path with minimum length contains the nodes of $u,v,w$ only and has length $2$. A path with maximum length contains all $n(=10)$ nodes and has length $n-1=9$. We denote the number of valid paths of length $l$ with $N_l$. The wanted number of all valid paths is \begin{align*} \sum_{l=2}^9N_l \end{align*}

• Length $l=2$: There is only one path $((u,w),(w,v))$ with length $2$, so $N_2=1$.

• Length $l=3$: We have $n-3$ ways to select a node $x$. We have two ways to place $w$, either between $u$ and $x$ or between $x$ and $w$. It follows $N_3=2(n-3)$.

• Length $l=4$: We have $(n-3)(n-4)$ ways to select two nodes and have $3$ ways to place $w$ in between.

Continuing this way we obtain with $n=10$ \begin{align*} &\color{blue}{N_2+N_3+\cdots N_9}\\ &\qquad=1+2(10-3)+3(10-3)(10-4)+4(10-3)(10-4)(10-5)\\ &\qquad\qquad+\cdots+8(10-3)(10-4)\cdots(10-8)\\ &\qquad=\sum_{l=2}^9(l-1)\frac{(10-3)!}{(10-l-1)!}\\ &\qquad\color{blue}{=95\,901} \end{align*} The final result was calculated with some help of Wolfram Alpha.

Note: If we consider these numbers with increasing $n=3,4,\ldots,\color{blue}{10},\ldots$ we obtain \begin{align*} 1,3,11,49,261,1\,631,11\,743,\color{blue}{95\,901},\ldots \end{align*} This sequence is archived as OEIS/A001339.

Answer 2

I guess it may not be passing through all the vertices, so simplest path is (u,w,v), another path may be (u,x,w,v)...

$\sum_{k=0}^{7}(k+1)\cdot\binom{7}{k}k!=\sum_{k=0}^{7}\binom{7}{k}(k+1)!$

So, $k$ is number of vertices not named $u,v$ or $w$.

$k+1$ is position of $w$ between the aditional vertices.

$\binom{7}{k}$ is to pick the vertices and $k!$ is to permutate them.

If path has to go through all of them then it is just formula for k=7, $\binom{7}{7}(7+1)!=8!$