If graph is tree what can be said about its adjacency matrix ?  Question If graph is tree what can be said about its adjacency matrix ?  And vice versa ?
Especially I am interested in case  when graph is bipartite graph.
Such graphs are related to error-correction codes (see e.g. Adjacency matrices of graphs as parity check matrices of error correcting codes ). 
If they are trees belief propagation is known to produce exact results.
 A: A graph is bipartite iff the odd powers of the adjacency matrix have all 0's on the diagonal.  So this implies that the sum of the $i$-th powers of the eigenvalues is 0 for each odd $i$.  Since the adjacency matrix is symmetric, it has real eigenvalues.  Thus, the eigenvalues are real numbers $\lambda_1,\dots ,\lambda_n $ with $\sum_{j=1}^n \lambda_j^i = 0$ for each odd $i$.  
I am guessing this probably should mean that the nonzero eigenvalues come in pairs of equal magnitude and opposite sign.  I wonder if there is a good trick for efficiently proving this sort of thing -- about collections of real numbers satisfying such an infinite family of relations?  (If so, I don't know this trick.)
${\bf Edit:}$ Douglas Zare proved my above conjecture as a comment, so it is true for bipartite graphs that the nonzero eigenvalues of the adjacency matrix come in pairs of equal magnitude and opposite sign. 
A: check the "matrix tree theorem"
So, a tree has only one spanning tree (which is itself of course), and conversely, if a graph has only one spanning tree, it must be a tree. Hence using the matrix tree theorem, which as you say counts the number of spanning trees, we can determine if a general graph is a tree or not. 
