MHB Number of Walks in K5 of Length 2: 15

[Joystar77]

Consider the complete graph with 5 vertices, denoted by K5.

F.) How many walks of length 2 are there in graph K5? Explain.

Is this correct as follows for the walks of length 2?

K squared (2) = K x K =

0, 1, 0, 1, 0
1, 0, 1, 0, 0
0, 1, 0, 1, 1
1, 0, 1, 0, 1
0, 0, 1, 1, 0

x

0, 1, 0, 1, 0
1, 0, 1, 0, 0
0, 1, 0, 1, 1
1, 0, 1, 0, 1
0, 0, 1, 1, 0

= 1, 0, 1, 0, 1
0, 1, 0, 1, 1
1, 0, 1, 1, 1
0, 1, 1, 1, 1
1, 1, 1, 1, 1

Is it true that in this problem, I would let the maximum walks of length k be 5 and the maximum number of nodes be 10.

 

[Ackbach]

I don't think your adjacency matrix is correct for $K_{5}$. See here. Now you must interpret the results. There are three walks of length $2$ from $1$ to $2$, four walks from $1$ back to $2$. You must do some fancy adding, while taking redundancies into account.

 

[Joystar77]

Ackback: I was following an example where it stated about the walks of length 2. I don't quite understand what your doing. Can you please explain further?

 

[Ackbach]

Sure. First of all, the adjacency matrix for $K_{5}$ is
$$A=\begin{bmatrix}0 &1 &1 &1 &1 \\ 1 &0 &1 &1 &1 \\ 1 &1 &0 &1 &1 \\
1 &1 &1 &0 &1 \\ 1 &1 &1 &1 &0 \end{bmatrix}.$$
This says that there is no edge from any vertex to itself, but there is exactly one edge from any vertex to any other vertex, which is exactly what $K_{5}$ is.

Secondly, there is a theorem that states that the number of walks of length $n$ from vertex $i$ to vertex $j$ is given by the $(i,j)$ entry in the matrix $A^{n}$. We are interested in walks of length $2$. Hence, we need to compute $A^{2}$, which is
$$A^{2}=\begin{bmatrix} 4 &3 &3 &3 &3 \\ 3 &4 &3 &3 &3 \\ 3 &3 &4 &3 &3 \\
3 &3 &3 &4 &3 \\ 3 &3 &3 &3 &4\end{bmatrix}.$$

Thirdly, the problem is asking for all the walks of length $2$. And here I need to retract what I said earlier about doing "some fancy adding, while taking redundancies into account." If, say, the $1,2,3$ walk is distinct from the $3,2,1$ walk, then all you need do is sum all of the entries in $A^{2}$. Moreover, the $(2,1)$ entry would represent different walks from the $(1,2)$ entry. So it's not as though you need to worry about the upper diagonal entries giving you redundant information to the lower diagonal entries. Don't worry if you don't understand what I just said. I'm trying to explain my own thinking, and where it went wrong.

I would just add up all the numbers in the $A^{2}$ matrix. What do you get?

 

[Joystar77]

When I add up what is inside of the adjacency matrix, I get the following:

4 + 3 + 3 + 3 + 3 = 16

3 + 4 + 3 + 3 + 3 = 16

3 + 3 + 4 + 3 + 3 = 16

3 + 3 + 3 + 4 + 3 = 16

3 + 3 + 3 + 3 + 4 = 16

16 + 16 + 16 + 16 + 16 = 80

Is 80 the right answer for the walks of length 2 in the graph K5?

 

[Ackbach]

When I add up what is inside of the adjacency matrix, I get the following:

4 + 3 + 3 + 3 + 3 = 16

3 + 4 + 3 + 3 + 3 = 16

3 + 3 + 4 + 3 + 3 = 16

3 + 3 + 3 + 4 + 3 = 16

3 + 3 + 3 + 3 + 4 = 16

16 + 16 + 16 + 16 + 16 = 80

Is 80 the right answer for the walks of length 2 in the graph K5?

I think you've got it.

 

[Joystar77]

Thank you Ackbach!