79 views
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?
| 79 views
0
Is it $720?$
0
i would be much more than that
0

@aditya333 what it should be according to you?

+4
no of vertices             total_paths

3                             1

4                              7C1 * 2!

5                            7C2  * 3!

6                              7C3  *4!

7                               7C4 * 5!

8                               7C5 * 6!

9                               7C6 * 7!

10                             7C7 * 8!

final answer would be summing up all these values
0
When you are taking number of vertices as 3, then it should be $^{10}C_3*3!$ for example when path length is 2(i.e. we have 3 vertices) suppose $u=1,v=2,w=3$ then there are 6 different ways are there.
0
the path starts at u and ends at w. So there is only 1 place to place v that is between u and w
0
I am taking vertex set as $V = \{1,2,3,4,5,6,7,8,9,10\}$.