The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+9 votes
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$?
asked in Graph Theory by Veteran (97.7k points)
retagged by | 554 views

2 Answers

+7 votes
Let us take the three vertices as $(1,2,10)$.

Now the simplest case is when only $3$ vertices are involved , i.e. $(1,2,10)=1$ way
Now we make room for one more vertex $(1, \_ ,2,10)$ or $(1,2,\_,10)$ which can be filled in $7$ ways giving a total of $7*2$ ways
For one more vertex we have $7*6*3$ ways and so on till we have accompanied all the $7$ vertices and along with $2$ a total of $8$ vertices are there with total ordering of $7!*8$

So, to sum it : $1+7*2+7*6*3+7*6*5*4+\ldots+7!*8 $

$\quad \quad = 7P0*1+7P1*2+7P2*3+\ldots+7P7*8$
answered by Junior (595 points)
edited by
nice explanation ,
I have a doubt. We select 3 vertices for u, v and w and then check the different paths. For an additional 1 vertex, we have 7 ways of selecting a vertex and 2! ways of placing it. Then, For additional 2 vertices other than u, v and w, we have 7*6 ways of selecting and 3! ways of ordering these 2 and w. Similarly For additional 3 vertices other than u, v and w, we have 7*6*5 ways of selecting and 4! ways ordering these 3 and w right. But your answer says different. Am I missing something?

You have given the no. Of paths by taking u,v,w as (1,2,10).

There might be many other possibilities for u,v,w like (1,3,10),(2,1,10)..... Because it is complete graph,there is a path between every two vertices.

So why total no. of paths are not multiplied by 10c3 ??

I think this question is to find out for a given u, v and w and not all the paths. I mean, we don't get to select u, v and w. We just need to find out the no. of paths given the vertices.

Ok thanks,got it.
please explain a little bit more

not getting this:-


For one more vertex we have 7∗6∗37∗6∗3 ways and so on till we have accompanied all the 77 vertices and along with 22 a total of 88 vertices are there with total ordering of 7!∗87!∗8

So, to sum it : 1+7∗2+7∗6∗3+7∗6∗5∗4+…+7!∗8
Explained very well !

+3 votes
there are 10 vertices in which U and V are initial and final vertices and W is intermediate vertex , so now remaining 7 vertices.

out of which we can select 0,1,2,3,...,7 at a time for simple path.

Case 1: 0 vertices out of 7 are selected then only one path(U->W->V)

Case 2: 1 vertex out of 7 are  selected then there will be 2 simple paths(U1WV and UW1V) =2!

and this vertex 1 may be selected in $\binom{7}{1}$


2 vertex out of 7 are  selected then there will be  3!   

and these vertex may be selected in $\binom{7}{2}$ and so on

Then Total simple paths= 1+ $\binom{7}{1}$ * 2! +  $\binom{7}{2}$ * 3! +  $\binom{7}{3}$ * 4! +  $\binom{7}{4}$ * 5! +  $\binom{7}{5}$ * 6! +  $\binom{7}{6}$ * 7! +  $\binom{7}{7}$ * 8!
answered by Active (3.4k points)

@Dharmendra Lodhi

Good Explanation sir...

In the  $_{}^{7}\textrm{C}_{2} \\$ case what are those 3! possibilities sir?

I was thinking U_ _ WV

                        UW_ _ V


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,814 questions
54,518 answers
75,293 users