This is probably well-known, but... Define the $n$-dimensional hypercube graph $H\_n$ as having for vertices the integers between 0 and $2^n-1$, and edges between integers differing by a power of 2. The characteristic polynomial of $H\_n$ is then $\prod\_{k=0}^n(x-n+2k)^{\frac {n!}{k!(n-k)!}}$, i.e. $(x-3)(x-1)^3(x+1)^3(x+3)$ for a cube, $(x-4)(x-2)^4x^6(x+2)^4(x+4)$ for a tesseract, etc. Is there a graph-theoretic proof of this result? 



Characteristic polynomial of hypercube graph
View the vertices as elements of $\mathbb{Z}^n$. If $a\in\mathbb{Z}^n$, define a function $f\_a$ on the vertices by
$$
 f\_a(x) = (-1)^{a^Tx}.
$$
This function is an eigenvectors and if $a$ has weight $w$, the eigenvalue is $n-2w$. I can make this look more combinatorial by viewing vertices (and $a$) as subsets of $\{1,\ldots,n\}$ and noting that $f\_a(x)$ is determined by the parity of $a \cap x$ (abusing notation).
Different choices of $a$ give linearly independent eigenvectors, so we get the multiplicities as well as the eigenvalues.


The actual difficulty with this question is in deciding what you mean by a "graph 
theoretical proof". From where I write, linear algebra is a standard and fundamental tool in graph theory.


Comment response: (too long for a comment box). OK. The $n$-cube is the Cartesian product of $n$ copies of $K\_2$.
The eigenvalues of the Cartesian product of two graphs $G$ and $H$ are the sums of the eigenvalues of $G$ with the eigenvalues of $H$. (The simplest way to see this is to note that the eigenvectors of the product are the Kronecker products of the eigenvectors of the factors.) Applying this $n$ times to $K\_2$ gives the desired result.


There are formulas for the effect on the characteristic polynomial adding edges or vertices, but they are not all simple, and I cannot see how to use them to get the eigenvalues of the $n$-cube. 


