This is a problem I'm having difficulty solving completely. It concerns a graph of m vertices with at least one vertex of degree m-1, which is neccessarily connected so its incidence matrix has rank m-1.
(i) If one considers an incidence matrix, Phi, over a field of characteristic 0, ie the incidence matrix of a directed graph where the columns correspond to the edges and each column contains exactly one 1, one -1, and remaining entries 0, (all zeroes for a loop). Any assignment of edge orientations is acceptable here.
Now forming the Gram matrix, Phi Phi', for the type of graph above one obtains the characteristic polynomial,
p(x) = x(a0 + a1 x + a2 x^2 + ... + x^m-2)(x-m)
where a0 = number of spanning trees = the product of the roots of the middle factor.
The roots for this type graph seem always to be integers (for the few examples I've tried), but I haven't been able to prove this.
(ii) Second this polynomial seems to be related to another characteristic polynomial of a full rank ExE matrix that describes the system of fundamental cut sets and cycles of the graph relative to any given spanning tree.
The formation of this matrix is involved: 1. Let Phi(i) be obtained by deleting the ith row.
2. Let G = -[(Phi(i)A' )^(-1)] [Phi(i)B'] where A' selects the columns of Phi corresponding the branches of a given spanning tree, and B' selects the columns corresponding to the chords. G then is |T|x|T^C| and describes the system of fundamental cuts and cycles.
3. Form the full rank ExE matrix, Theta = I + (A'GB - B'G'A) = I + S, where the second terms on the right are skew symmetric. This is another way of describing the system of fundamental cuts and cycles of a given spanning tree. I was able to show that the determinant of Theta is the number of spanning trees by induction on the number of edges.
Now the characteristic polynomial of S has the form
f(y) = y^k(c0 + c2 y^2 + c4 y^4 + ... + y^2n)
where E = 2n + k and the the sum of the coefficients c0 + c1 + c4 + ... + 1 is the number of spanning trees.
If we rewrite the second factor as
h(x) = c0 + c1 x + c2 x^2 + ... + x^n
and pad h(x) with enough zero roots if neccessary so that its degree is m-2 where m is the number of vertices, then in regards to (i) above
p(x) = x h(1-x) (x-m)
But I can't prove this nor can I show that the roots of h(x) are also always integers. Also we only have m-1 <= 2n+k <= m(m-1)/2, but this admits the possibility that n > m-2 and in the few examples I've tried this never happens. I've haven't tried many examples though.