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

  • $\begingroup$ You dont need $\binom{10}{2}$, $\endgroup$ Sep 22 '17 at 10:48
  • $\begingroup$ @DjuraMarinkov why not $\binom {10}{2}$ , we will not select $u$ and $v$ from avaliable $10$vertex? $\endgroup$
    – laura
    Sep 22 '17 at 10:52
  • $\begingroup$ 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 $\endgroup$ Sep 22 '17 at 11:31
  • $\begingroup$ 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 $\endgroup$ Sep 22 '17 at 11:37

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.

  • $\begingroup$ 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! $\endgroup$
    – laura
    Sep 22 '17 at 12:00
  • $\begingroup$ @Laura: Thanks! Typo corrected. $\endgroup$
    – epi163sqrt
    Sep 22 '17 at 12:02
  • $\begingroup$ Yes, we both have kinda bumpy explanation. It's simply take k additional vertices and permutate them along with w $\endgroup$ Sep 22 '17 at 20:57
  • $\begingroup$ @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. $\endgroup$
    – epi163sqrt
    Sep 23 '17 at 16:45
  • $\begingroup$ 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 $\endgroup$ 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)...


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.