Kenneth Rosen Edition 6th Exercise 8.4 Question 17d (Page No. 575)

Question

The number of paths of length 5 between two different
vertices in K4 (complete graph)?

Comments

if only repeation of edge is allowed,we can have length 5.

so,from A-B,there are 3 paths of length 5

similarly, A-C , A-D , C-D , C-B , B-D have 3 paths of length 5.

is it correct?

---

We can solve this problem with help of adjacency matrix of K₄  :

to find the path of length 5 b/w two different vertices  we have to find the value of any non-diagonal element of the matrix (K₄)⁵ (that one is a long method though, so i was finding a simpler one)

btw answer for this one is 61...

Answer 1

Adjacency Matrix of Complete Graph with 4 vertices A =  $\begin{bmatrix} 0 & 1& 1& 1\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 1& 1& 1& 0 \end{bmatrix}$

The number of paths of length five from i^th vertex to j^th vertex is the (i, j)th entry of A^5.

After Calculation A5 = $\begin{bmatrix} 60 & 61& 61& 61\\ 61& 60 & 61& 61\\ 61& 61& 60& 61\\ 61& 61& 61& 60 \end{bmatrix}$

Total number of paths  of length five from i^th vertex to j^th vertex such that (i$\neq$j)= 61

Comments

how to calculate $A^{5}$ in minimum time ? any shortcut