edited by
742 views
1 votes
1 votes
Let K$_n$ be such that the vertices are labeled 1,2,3,...n.

The number of simple paths between v$_1$ and v$_n$ such that the labels on the path are strictly increasing ____________________
edited by

1 Answer

Best answer
4 votes
4 votes

Note that given is Complete graph ===> there is a edge between every pair of vertices.

we have n vertices, let name them as V1,V2,...Vn.

We want the paths between V1 and Vn.

there are remaining, n-2 elements, i.e., V2,V3,....Vn-1 . ===> let the Set S = { remaining elements } ===> |S| = n-2.

what is the Power Set of this elements ===> size of power Set of S = 2n-2.

in the power set, each set is lead to unique path ( labels are in the path are strictly increasing order ) between V1 and Vn.

∴ No.of Simple paths between V1 and Vn Such that the labels in the path are strictly increasing order = 2n-2.

 

ex:-

let take K5..... name the labels as V1,V2,V3,V4,V5.

We want the simple paths between V1 and V5.

remaining vertices are {V2,V3,V4}, then the power set is contains the following set

1) ∅ ====> the path which we required is V1 --- V5.

2) { V2 } ====> the path which we required is V1 --- V2 --- V5.

3) { V3 } ====> the path which we required is V1 --- V3 --- V5.

4) { V4 } ====> the path which we required is V1  --- V4 --- V5.

5) { V2,V3 } ====> the path which we required is V1 --- V2 --- V3 --- V5.

6) { V2,V4 } ====> the path which we required is V1 --- V2 --- V4 --- V5.

7) { V3,V4 } ====> the path which we required is V1  --- V3 --- V4 --- V5.

8) { V2,V3,V4 } ====> the path which we required is V1 --- V2 --- V3 --- V4 --- V5.



Now i am interested in that,what the formula if in the question the restriction " labels are in the path are strictly increasing order " removed ?

the power set contains = 2n-2. sets

we can partition them as

$\binom{n-2}{0} + \binom{n-2}{1} + \binom{n-2}{2} + ...+ \binom{n-2}{n-2}$ = 2n-2.

$\binom{n-2}{0}$ ===> lead to 1 permutation paths

$\binom{n-2}{1}$ ===> lead to 1 permutation paths

$\binom{n-2}{2}$ ===> lead to 2 permutation paths

............

$\binom{n-2}{n-2}$ ===> lead to (n-2)! permutation paths

∴ No.of Simple paths between V1 and Vn  = $\binom{n-2}{0} * 1! + \binom{n-2}{1} * 1! + \binom{n-2}{2} * 2! + ...+ \binom{n-2}{n-2} * (n-2)! $.

selected by

Related questions

0 votes
0 votes
1 answer
1
Hakuna Matata asked May 4, 2018
427 views
Given 3 connected components with 2,2,3 vertices. In how many ways can we add two edges to connect the whole graph?Also, if possible generalise the method for graph with ...
4 votes
4 votes
2 answers
4
Balaji Jegan asked Nov 27, 2018
2,498 views
How many ways are there to color this graph from any $4$ of the following colors : Violet, Indigo, Blue, Green, Yellow, Orange and Red ?There is a condition that adjacent...