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

You give more info and so will I :-)

-
Thanks for reply. That is my test. It is returned back without any comment or explanation. how can I upload the original paper? I scanned but don't know how to upload. –  user73195 Apr 18 '13 at 12:27
That was your test? Or is this a sample test? What do you not understand? –  Jp McCarthy Apr 18 '13 at 12:31
It'd be great if you could add more to the question, but I don't think adding a scanned copy of your returned test is the way to go about it. Perhaps you could just type in your thoughts on the questions? (New users cannot add images; this restriction is removed at 10 reputation.) –  Douglas S. Stones Apr 18 '13 at 12:37