Every power of adjacency matrix contains zeroes I need to find connected graph $G = (V, E), |V| \geq 3$ such that every power of his adjacency matrix contains zeroes.
I know that that graph will be path and adjacency matrix for even and odd powers would look like this (lets say for $|V| = 3$):
$M=
  \left[ {\begin{array}{ccccc}
   0 & 1 & 0\\
   1 & 0 & 1\\
   0 & 1 & 0\\
  \end{array} } \right]
$
$
  M*M=
  \left[ {\begin{array}{ccccc}
   1 & 0 & 1\\
   0 & 2 & 0\\
   1 & 0 & 1\\
  \end{array} } \right]
$
$
  M*M*M=
  \left[ {\begin{array}{ccccc}
   0 & 2 & 0\\
   2 & 0 & 2\\
   0 & 2 & 0\\
  \end{array} } \right]
$
$
  M*M*M*M=
  \left[ {\begin{array}{ccccc}
   2 & 0 & 2\\
   0 & 4 & 0\\
   2 & 0 & 2\\
  \end{array} } \right]
$
etc...
Zeroes and other numbers are changing their position for even/odd powers of matrix.
I don't know how to prove that there always will be zero for path graph with $n$ vertices for any power of his adjacency matrix. Maybe use an induction(I am not sure how to proceed with induction though)? 
 A: Hint: if the graph is bipartite (with parts $A$ and $B$), any walk  starting in part $A$ will be in part $B$ after an odd number of steps and in part $A$ after an even number of steps.
A: The crux of Robert Israel's hint is that a bipartite graph has no cycle of odd length. So a walk follows a sequence of edges, where we can repeat vertices. Now suppose $G$ is bipartite and we can walk from $v_{i} \to v_{j}$, where $v_{i}, v_{j}$ are in the same partition. The proof is essentially by algorithm. We begin walking at $v_{i}$. We move along one of $v_{i}$'s edges to a vertex $v_{2}$ in the second partition. Then since $v_{2}$ isn't adjacent to any vertex in its partition, you go back to a vertex in the first partition. So following this algorithm, it must take an even number of steps to start and end in the same partition, and an odd number of steps to start and end in opposite partitions.
Now if there is a cycle of odd length, we can follow that cycle to get a $v_{i}, v_{j}$ walk of odd length. Because in a bipartite graph, there is no such cycle, we cannot construct a walk of odd length to two vertices in the same partition.
