Powers of Adjacency Matrix (Determination of connection in Graph)

Question

I am studying graph theories, and I am not sure about how power of adjacency works. I know $k$-th powers of A tells connection in graph, and I can read lengths between a vertex to vertex after taking powers of adjacency. My question is: why can powers of adjacency matrix determine connections in graph, and how many powers need to determine it?

Answer 1

I will give you a hint on how to proceed.

As you mentioned, the entries of the adjacency matrix gives you the connections between vertices. If you take powers, then you are really concatenating walks. The $ij$th entry of the $k$th power of the adjacency matrix tells you the number of walks of length $k$ from vertex $i$ to vertex $j$.

To prove this using induction, try this fact.

To form a walk of length $k+1$ from vertex $i$ to $j$, you must first have a walk of length $k$ from vertex $i$ to some vertex $v$ and then a walk of length $1$ from vertex $v$ to vertex $j$.