# Proving that the characteristic polynomial of a bipartite graph has alternating positive and negative coefficients

It is well known that the characteristic polynomial of a bipartite graph is of the form

$\sum_{k=0}^n (-1)^kc_{2k} x^{2k}$ where $c_{2k} \geq 0$.

I can prove why there cannot be any odd powered coefficients in the characteristic polynomial but cannot find a way to prove that the coefficients of the remaining terms alternate sign.

I have tried working with Sachs Theorem which states that for a graph $G$ the coefficients $a_k$ are given by

$a_k(G) = \sum_{S \in L_k} (-1)^{\omega(S)}2^{c(S)}$

where $L_k$ denotes the set of subgraphs of G composed only of cycles and disjoint edges, $\omega(S)$ is the number of connected components in S and $c(S)$ is the number of cycles.

However, counting up all of the possible graphs and their contributions (particularly with different labellings) has proved tedious and tricky and I am wondering if there is a better way to approach the proof which I have not seen yet.

Thanks!

-
The title is slightly misleading; the polynomial doesn't actually have alternating positive and negative coefficients; "alternating non-negative and non-positive even-numbered coefficients" would be correct, though slightly lengthy :-) – joriki Dec 20 '12 at 11:59
One thing you could try is use the fact that if $G$ is a bipartite graph and $\lambda$ is an eigenvalue with multiplicity $m$ then $-\lambda$ is also an eigenvalue of $G$ with same multiplicity $m$ along with the fact that the $k'$th coefficient of the charpoly is just the sum of the product of all possible choices of $k$-eigenvalues from the (multi)set of all eigenvalues. – Jernej Dec 20 '12 at 12:46

Second, if $G$ is bipartite we can write its adjacency matrix in partitioned form $$A =\begin{pmatrix}0&B^T\\ B&0 \end{pmatrix};$$ since $$\begin{pmatrix}-I&0\\0&I\end{pmatrix}\begin{pmatrix}0&B^T\\ B&0 \end{pmatrix}\begin{pmatrix}-I&0\\0&I\end{pmatrix} =\begin{pmatrix}0&-B^T\\-B&0\end{pmatrix}$$ we see that $A$ and $-A$ are similar. Hence if $\lambda$ is an eigenvalue of $A$ with multiplicity $k$, so is $-\lambda$. It follows that the characteristic polynomial if a power of $x$ times a product of terms of the form $x^2-\lambda^2$.