The Gateway to Computer Science Excellence
0 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?
in Graph Theory by | 113 views
Is it $720?$
i would be much more than that

@aditya333 what it should be according to you?

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
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.
the path starts at u and ends at w. So there is only 1 place to place v that is between u and w
I am taking vertex set as $V = \{1,2,3,4,5,6,7,8,9,10\}$.

1 Answer

0 votes
is it 60621?

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
52,345 questions
60,487 answers
95,294 users