ISI 2019 | PCB CS | Question: 2

Question

Let $K_{n}$ denote the complete graph on $n$ vertices, with $n \geq 3$, and let $u, v, w$ be three distinct vertices of $K_{n}$. Determine the number of distinct paths from $u$ to $v$ that do not contain the vertex $w$.

Comments

A path between two vertices is defind as a sequence of edges such that no vertex gets repeated.

In a complete graph $K_n$, every vertex is connected with all remaining $n-1$ vertices.

Below, each $\circ$ represents an empty space in our path, which can be occupied by any of the remaining $n-3$ vertices such that it is nor repeated.

$u - v$

#Length $1$ paths = $1$

$u - \circ - v$

#Length $2$ paths = ${n-3 \choose 1} * 1!$

$u - \circ - \circ - v$

#Length $3$ paths = ${n-3 \choose 2} * 2!$

$u - \circ - \circ - \circ - v$

#Length $4$ paths = ${n-3 \choose 3} * 3!$

.

.

.

#Length $n-2$ paths = ${n-3 \choose n-3} * (n-3)!$

We can also write - #Length $1$ paths = ${n-3 \choose 0} * 0!$

$\therefore$ Total distinct paths = $\sum_{k=0}^{n-3} (k! * {n-3 \choose k})$

@Deepak Poonia sir @Kabir5454, is this correct and what else can we do further to represent answer in closed form??

---

$\sum_{k=0}^{n-3}\left ( k!*\binom{n-3}{k} \right )$

Let $z=n-3$

$\sum_{k=0}^{z}\left ( k!*\binom{z}{k} \right )$

=$\sum_{k=0}^{z}\left ( \frac{z!}{(z-k)!} \right )$

$S(z)=zP0+zP1+zP2+ZP3+…….+ZPZ$

$S(z)=1+z+z(z-1)+z(z-1)(z-2)+……...z!$

 $S(z)=1+z(1+(z-1)+(z-1)(z-2)+……...+(z-1)!)$

$S(z)=1+zS(z-1)$  

We can make some close form like this .

---

@shishir__roy It is correct.

If we interpret the final expression using a combinatorial argument, it is basically the number of Ordered Subsets of a set of $n-3$ elements. It seems that we do not have an easy expression in terms of $n$ for this.

https://math.stackexchange.com/questions/1715880/how-many-ordered-subsets-of-a-set

But it is good alternative way of looking at the given problem, that every permutation of every subset of the remaining $n-3$ elements is going to give a distinct path between $u,v.$

Please convert your comment into an answer, with additional insights from this discussion.

Answer 1

A path between two vertices is defined as a sequence of edges such that no vertex is repeated.

In a complete graph $K_n$, every vertex is connected with all other $n-1$ vertices.

 

Below, each $\circ$ represents a placeholder in our path, which can be occupied by any of the remaining $n-3$ vertices such that it is not repeated.

Length $1$ paths are of the form : $u - v$

No. of length $1$ paths = $1$

 

Length $2$ paths are of the form : $u - \circ - v$

No. of length $2$ paths = ${n-3 \choose 1} * 1!$

ie we choose $1$ vertex from the remaining $n-3$ vertices and chosen vertex can permute in $1!$ way.

 

Length $3$ paths are of the form : $u - \circ - \circ - v$

No. of length $3$ paths = ${n-3 \choose 2} * 2!$

ie we choose $2$ vertices from the remaining $n-3$ vertices and chosen vertices can permute in $2!$ ways.

 

Length $4$ paths are of the form : $u - \circ - \circ - \circ - v$

No. of length $4$ paths = ${n-3 \choose 3} * 3!$

ie we choose $3$ vertices from the remaining $n-3$ vertices and chosen vertices can permute in $3!$ ways.

.

.

.

No. of length $n-2$ paths = ${n-3 \choose n-3} * (n-3)!$

ie we choose $n-3$ vertices from the remaining $n-3$ vertices and chosen vertices can permute in $(n-3)!$ ways.

 

We can re-write : No. of length $1$ paths = ${n-3 \choose 0} * 0!$

 

$\therefore$ Total no. of distinct paths = $\sum_{k=0}^{n-3} \left( kk! * {n-3 \choose k} \right)$.

Assume $z=n-3$, we can now re-write : Total no. of distinct paths $= T(z) = \sum_{k=0}^{z} \left( k! * {z \choose k} \right) = \sum_{k=0}^{z} \left( \frac{z!}{(z-k)!} \right)$

$\therefore T(z) = 1 + z + z(z-1) + z(z-1)(z-2) + … + z*(z-1)!$

$\therefore T(z) = 1 + z * \left( 1 + (z-1) + (z-1)(z-2) + … + (z-1)! \right)$

$\therefore T(z) = 1 + z * T(z-1)$.

The above recurrence relation $T(z)$ with base case $T(0) = 1$ gives the number of distinct paths in $K_n$ graph from $u$ to $v$ that do not contain $w$ and $z = n-3$.