# Math Help - Graph Theory

1. ## Graph Theory

I'm stuck with the following problem.. any ideas?

Find the number of walks of length n between two different, predetermined vertices in
K4 if n is:
i) 2
ii) 3
iii) 4
iv) 5
Define a recurrence relation for pn where pn is the number of walks of
length n between two different, predetermined vertices in K4.

I got that for n=2, there are two walks, for n=3 there are 5 paths, for n=4 there are 12....

Are these right? Can you help me get the recurrence relation?

Thanks!

2. The adjacency matrix for $K_4$ is $A_{K_4 } = \left( {\begin{array}{cccc} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \\\end{array}} \right)$.
The third power is $\left( {A_{K_4 } } \right)^3 = \left( {\begin{array}{cccc}
6 & 7 & 7 & 7 \\ 7 & 6 & 7 & 7 \\ 7 & 7 & 6 & 7 \\ 7 & 7 & 7 & 6 \\ \end{array}} \right)$
.

So it appears the your calculation for $n=3$ is two off.
If you square the matrix, you will see that you are correct for $n=2$.

Suppose that $S_n$ denotes the number of paths of length n from a vertex to itself. Clearly $S_2 = 3$ because each point is adjacent to three other vertices. Here is an example: ABA, ACA, & ADA.

Suppose that $T_n$ denotes the number of paths of length n between two vertices.
Consider the two vertices D & B in the graph. If we want to know the number of paths of length (n+1) from D to B, then we must go through vertex A or C. So we can use any one of the $T_n$ paths from D to A of length n and add AB to any one. We have the same idea using vertex C. But we can also go directly to B from D by using any path from D to D of length n.
Thus we get $T_{n+1}= 2T_n + S_n$

Now we need to find $S_n$ in terms of $T_{n-1}$.
Any path from D to D of length n has the last edge AD, BD, or CD.
So count the number of the number of paths of length n-1 between two vertices.
Thus we have $S_{n}= 3T_{n-1}$ or $T_{n+1}= 2T_n + 3T_{n-1}$.