edited by
3,055 views
14 votes
14 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$?
edited by

3 Answers

19 votes
19 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}$

   similarly

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!
10 votes
10 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$
edited by

Related questions

1 votes
1 votes
4 answers
1
go_editor asked May 23, 2016
997 views
A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Show that any finite simple graph has at least...
13 votes
13 votes
5 answers
3
2 votes
2 votes
2 answers
4
go_editor asked May 19, 2016
612 views
Let $G$ be a graph in which each vertex has degree at least $k$. Show that there is a path of length $k$ in $G$—that is, a sequence of $k+1$ distinct vertices $v_0, v_1...