Let $G$ be any simple and undirected graph. Let $A$ be the adjacency matrix of $G$.

1) Let $B$ be the number $\tfrac16\mathrm{tr}(A^3)$. What does $B$ count? That is $B$ counts the number of....?

2) Suppose that $M$ is adjacency matrix of a tree. Explain why every element of the diagonal of $M^3$ must be zero.

3) Must every element of the diagonal of $M^2$ be zero?

-
Just a short comment on 3, it is easy to prove that, in a simple graph, the diagonal entries of $M^2$ are exactly the degrees of the vertices. To understand why, think: how can you get from vertex $v$ to the same vertex in exactly 2 steps? – N. S. Apr 24 '13 at 14:54

Let me extend the answer of Jp McCarthy. If $A$ is the adjacency matrix of $G$ then $X=A^k$ denotes the paths in $G$ in such a way that if $x_{i,j}=\ell$ then there are $\ell$ paths of length $k$ connecting vertex $i$ and $j$. Notice that the paths doesn't have to be simple, i.e., vertices and edges can be reused.

Regarding you questions:

1. A diagonal entry encodes the cycles of length 3. For length 3, no path can reuse an edge or vertex. You count every 3-cycle 6 times (3 starting vertices and two orientations).
2. A tree has no cycles, so no 3-cycles, therefore every entry on the diagonal of $M^3$ is zero.
3. Every vertex not isolated is incident to at least one 2-cycle (go back and forth along one edge). So the answer is no. Indeed, if the tree is a spanning tree, none of the entries will be zero.
-
I am an immigrant. sometimes, when the time out, my professor speaks too fast, I don't completely understand what he is talking about. I can read it carefully and slowly to get the stuff from your explanation. Thank you very much. – user73195 Apr 18 '13 at 16:41

I think...

1. Number of three cycles

2. No cycles

3. No