# Powers of Adjacency Matrix (Determination of connection in Graph)

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?

-
You should try to prove this by induction. It's a good exercise. – wj32 Nov 7 '12 at 2:25
So say nth power of adjacency is a connected graph. Start with base step that saying when n=1, (P(n) (any nth power of adjacency matrix determines n-th connection in graph), P(1)=A^1 is true (Which means graph is connected, and nth tells length). And go to induction step that P(n)=A^n is true then P(n+1)=A^(n+1) is also true? – Uka Nov 7 '12 at 2:47

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 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$.