The Gateway to Computer Science Excellence
0 votes
113 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?
in Graph Theory by | 113 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\}$.

1 Answer

0 votes
is it 60621?
by

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
201,823 comments
95,294 users