ISI kolkata MTech CS 2019

Question

Let $K_n$ denote the complete graph on $n$ vertices, with $n ≥ 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$.

Answer 1

A complete graph with $n$ vertices (i.e. $K_n$) have $C^n_2$ edges.

now, distinct paths between two vertices in $K_n$ = path goes through its direct neighbors + path goes through remaining complete graph (i.e. excluding source and destination)

assume in the above $K_5$ graph source is $b$ and destination is $a$

$\therefore$ path goes through $b$'s neighbors = $n-1$ = $4$

Remaining path goes through complete graph forming by $cde$ (i.e. $K_3$ excluding source and destination)

$\therefore$ remaining paths = number of edges in $K_{n-2}$ (i.e. for $K_{cde}$) = $C^{n-2}_2$ = $C^3_2$ = $3$

$\therefore$ total paths between $ba$ = $(n-1)$ * $C^{n-2}_2$ = $4*3$ = 12

Now, according to question, one vertex $w$ has been excluded from the path.

Then after excluding $w$ from $K_n$, the graph become $K_{n-1}$

$\therefore$ total paths between $ba$ for $K_{n-1}$ = $n-2$ * $C^{n-3}_2$