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

## 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

• You dont need $\binom{10}{2}$, Sep 22 '17 at 10:48
• @DjuraMarinkov why not $\binom {10}{2}$ , we will not select $u$ and $v$ from avaliable $10$vertex? Sep 22 '17 at 10:52
• are not them already defined? Why would you choosing them? You have some specific vertices u,v,w, you dont choose them you choose other vetices. And also I dont see path must go through all vertices Sep 22 '17 at 11:31
• I see what you are doing, you are choosing which of them you want to call u,v,w. I dont think it is what is needed. Your path starts wit a specific vertex named u and ends with specific vertex named v. And also it contains vertex named w. That is why I think path may be less than 10 vertices long. Otherwise every path would contain w anyway Sep 22 '17 at 11:37

## 2 Answers

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.

• Length $l=2$: There is only one path $((u,v),(v,w))$ with length $2$, so $N_2=1$. Here it should be $((u,w),(w,v))$ ...right? because w is intermediate i guess! Sep 22 '17 at 12:00
• @Laura: Thanks! Typo corrected. Sep 22 '17 at 12:02
• Yes, we both have kinda bumpy explanation. It's simply take k additional vertices and permutate them along with w Sep 22 '17 at 20:57
• @DjuraMarinkov: I do not see that great difference. When looking at your first expression, then the right-hand side corresponds to your comment above, while the left-hand side are the two lines of explanation in your answer. I would consider both explanations nearly of the same value. Sep 23 '17 at 16:45
• It is same, just wanted to point on no need to separately permutate additional vertices and then adding $w$ between. The second explanation is smoother Sep 23 '17 at 17:01

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

• I just now recognized that our solutions are essentially the same. (+1) Sep 22 '17 at 16:07