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. 
 A: 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.
A: 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...
