Graph Theory characteristic polynomial problem

[Stephen Kauffman]

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.

I've posted a paper I've written,
http://www.bcpl.net/~smkauffm/gtlawatersigned.pdf , which discusses these
two seemingly related polynomials in section 5.1 page 18, and section 7.1
page 37.

Any ideas, or where the problem has been treated before?
--
Stephen Kauffman
[e-mail]
http://himthealmightypowerhurled.blogspot.net