characteristic polynomial of graph I have 2 questions about how to find the characteristic polynomial of some graphs.


*

*If G is a simple cycle with n vertices and n edges, $C_n$, I need to find the characteristic polynomial of $C_n$ (the characteristic polynomial of the adjacency matrix).


I tryed to find some reccursive equation to the characteristic polynomial of the adjacency matrix:
$$
        \begin{pmatrix}
        0 & 1 & 0 & & \cdots & 0 & 1 \\
        1 & 0 & 1 & 0 & \cdots & 0 & 0\\
        0 & 1 & 0 & 1 & 0 & \cdots & 0 \\
        \vdots && \ddots & \ddots& \ddots& \ddots   \\
        0 && &&&&1\\
        1 &0&&&0&1&0\\ 
        \end{pmatrix}
$$
but I didn't succeed.
\2.  I have a graph G that is k-regular, and I need to prove a connection between characteristic polynomials of G and G complement, $\overline G$:
$$ p_\overline G(x) = (-1)^n{x-n+k+1\over x+k+1}p_G(-x-1) $$
 A: Jesus revealed this answer to me the following for the second part
I supply the answer for part two
the Let $x_i$ be the eigenvalue of $X$, then $$\Phi (X, x)=\displaystyle  \prod _{i=1} ^{n} (x-x_i)= (x-x_1)\prod _{i=2} ^{n} (x-x_i) = (x-k)\prod _{i=2} ^{n} (x-x_i)$$
It follows from this that
  $$\Phi (X, -x-1)=\displaystyle   (-x-k-1)\prod _{i=2} ^{n} (-x-1- \theta _i)$$
  Similarly we calculate 
  \begin{align*}
  \Phi (\overline{X}, x) &=\displaystyle  \prod _{i=1} ^{n} (x-x_i)\\ &= (x-x_1)\prod _{i=2} ^{n} (x-x_i)\\  &= (x-(n-k-1))\prod _{i=2} ^{n} (x-(-1-\theta _i))\\ &=  (x-n+k+1) \prod _{i=2}^{n}(x+1+\theta_i)\\  &=  (x-n+k+1) \frac{n+k+1}{n+k+1} \prod _{i=2}^{n}(x+1+\theta_i)\\ &=  (x-n+k+1) \frac{n+k+1}{n+k+1} \left( -1 \right) ^{n-1}  \prod _{i=2}^{n}(-x-1-\theta_i)\\ &=  \left( -1 \right) ^{n} \frac{n+k+1}{x-n+k+1}  (-x-k-1) \prod _{i=2}^{n}(-x-1-\theta_i)\\ &=  \left( -1 \right) ^{n} \frac{n+k+1}{x-n+k+1}  \Phi (X, -x-1)
  \end{align*}\\
Hence we can write $\displaystyle  \Phi (\overline{X}, x)= \left( -1 \right) ^{n} \frac{n+k+1}{x-n+k+1}  \Phi (X, -x-1) $second part
