# Connected graph, each power of adjacency matrix has zeros

Could you help me with the following?

Find a connected graph for which each of the matrices $A^{k}_{G}, \ k \ge 0$ contains $0$s.

And another one:

Show that a graph is connected if and only if $(I+A_{G})^{n}$ doesn't contain $0$s for $n$s large enough.

I know that in a matrix $A^{k}_{G} \ \ a_{ij}^{k}$ is the number of walks length k from $v_{i}$ to $v_{j}$. And if we multiply matrices we are simply concatenating walks. But I don't know how (or if) we can use it proving the first one.

As to the second one I am completely at loss.

-

HINT: For the first question, consider the graph with two vertices and one edge. More generally, consider any bipartite graph. The point is that a walk with ends in different vertex sets has odd length, while a walk with ends in the same vertex set has even length.

One direction of the second question is easy. For the other direction, suppose that $G$ is connected. Then there is a positive integer $m$ such that for any two vertices $u$ and $v$ of $G$ there is a walk from $u$ to $v$ of length at most $m$. Show that $(I+A_G)^n$ has no zeroes if $n\ge m$. The key is to show that the $(i,j)$ entry in $(I+A_G)^n$ is the number of walks of length at most $n$ from $v_i$ to $v_j$. Try it first for $n=2$; try to see why the $1$’s on the main diagonal of $I+A_G$ correspond to standing in place on a vertex for one ‘step’ instead of actually moving to a different vertex.

-
So what you mean is that no matter how many times should we concatenate walks in a bipartite graph, there will always be some vertices which won't be connected, right? –  Hagrid Jan 13 '13 at 18:09
@Hagrid: If $u$ and $v$ are in different vertex sets, there is no walk from $u$ to $v$ of length $0,2,4,6,\dots$, so you’ll get a $0$ in the corresponding entry of $A_G^{2n}$ for all $n\ge 0$. And if $u$ and $v$ are in the same vertex set, ... ? –  Brian M. Scott Jan 13 '13 at 18:11
Well, if $u$ and $v$ are in the same set of vertices of a bipartite graph, then the can't be connected, then from the way we multiply matrices we know that if $a_{ij}=0$, then $a_{ij}^{k}=0$ –  Hagrid Jan 13 '13 at 18:16
@Hagrid: No, there may well be walks from $u$ to $v$; they just have to have even length. Thus, the appropriate entry in $A_G^{2n+1}$ will always be $0$. Since you’re having trouble with this, I strongly suggest that you look at the simplest example, the graph with two vertices and one edge. Its adjacency matrix is $A=\pmatrix{0&1\\1&0}$. What are the powers of $A$? You can easily compute them by hand. –  Brian M. Scott Jan 13 '13 at 18:19
@Hagrid: You have the powers right, but I don’t think that you’re interpreting them correctly. There are just two vertices, say $v_1$ and $v_2$. You have $A^n=A=\pmatrix{0&1\\1&0}$ for all odd $n$; this means that if $n$ is odd, there is no walk of length $n$ from $v_1$ to $v_1$ or from $v_2$ to $v_2$, but there is one from $v_1$ to $v_2$. You have $A^n=I$ for all even $n$; this means that if $n$ is even, there is no walk of length $n$ from $v_1$ to $v_2$, but there is one from $v_1$ to $v_1$ and from $v_2$ to $v_2$. All of these facts should also be pretty clear when you look at $G$: $*-*$. –  Brian M. Scott Jan 13 '13 at 18:35

Hint: Each power $k$ gives you the number of paths of $k$ legnths between vertices $i,j$ for the matrix entry $a_{ij}$. You can think of graphs that restrict some kind of paths, for example bipartite graphs: two vertices of the same set can only have paths of even length, and two of different sets can only have paths of odd lengths...

-