# Graph theory and Adjacency matrices

• Find a connected graph of n vertices for which each of the powers AG^1 , AG^2 , . . . of the adjacency matrix contains some zero elements.

for this I drew two vertices and linked them together with one edge, then I built the adjacency matrix with rows (0 1) and (1 0). I showed that for n>1, AG^n is the identity matrix thus containing some zero elements. I just have not proved this for n vertices, I'm just at two. Can I take a step further and say that any n vertices connected in a straight line satisfy the conditions ?

• The path with one edge can also be thought of as the complete graph $K_2$, the complete bipartite graph $K_{1,1}$, or the unique tree on two vertices. So these four families, as well as any others you can think of, are natural ways to try to extend your observations to $n$ vertices. (Also, your calculation as stated is not correct: for the path with one edge, $AG^k=I$ only for even $k$. But that's good enough to get what you want: what happens for odd $k$?) – Eric Stucky Nov 3 '16 at 0:32

I think you example works for all $n>1$(though your calculation is indeed not correct as pointed in the first comment). To prove it, enumerate the vertices with $1,2,\ldots ,n$. The entry $(u,v)$ of the matrix $AG^i$ contains the number of paths of length i between u and v in the graph G. Then for each i, either the entry (1,1) or (1,2) is 0, since all the paths starting at 1 and going back to 1 are of even length and all such paths from 1 to 2 are of odd length.
Another good example will be the graph having one vertex connected to all the other $n-1$ vertices with one edge each(and no other edges in the graph). You can try to do similar reasoning here for odd/even length of certain paths.