Sum of adjacency matrix of a graph

Question

I really need help to solve this problem since I don´t know where to start:

For A ∈ Mn×n(Z) we define $A^0 = I_n$ (the identity matrix). Let G a graph, prove that G is connected if and ony if exists a r ∈ N such that

$\sum_{i=0}^r A^i_G$

is a matrix with all its entries are different from 0, where $A_G$ is the adjacency matrix of G.

thank you for your time :D.

Answer 1

Hint

Use the fact that a graph is connected if and only if, between any two distinct vertices there exists a path. What is the largest possible length of a path in a graph with $n$ vertices?