## 403 – HW 4 – Algebraic graph theory

This set is due Thursday, May 15, at 11am.

1. (Norman Biggs, Algebraic Graph Theory, Proposition 2.3) Let $\Gamma$ be a (finite, simple) graph with $n$ vertices, and let $A$ be its adjacency matrix. Suppose that the characteristic polynomial of $A$ is ${\rm char}_A(x)=x^n+c_1x^{n-1}+c_2x^{n-2}+\dots+c_n$. Verify that:

1. $c_1=0$.
2. $-c_2$ is the number of edges in $\Gamma$.
3. $-c_3$ is twice the number of triangles in $\Gamma$.

2.  (Chris Godsil, Gordon F. Royle, Algebraic Graph Theory, Theorem 8.5.1) Let $G$ be a finite simple graph on $n$ vertices that is $k$-regular, that is, such that each vertex has degree $k$. Suppose $G$ has $n$ vertices and $A$ is its adjacency matrix.

1. Verify that $k$ is an eigenvalue of $A$.
2. Let $\lambda_2,\dots,\lambda_n$ be the other eigenvalues of $A$. Let $\bar G$ denote the complementary graph to $G$: This graph has the same vertices, but two vertices are joined by an edge iff they are not joined by an edge in $G$. Let $B$ be the adjacency matrix of $\bar G$. Show that there is a basis of $\mathbb R^n$ consisting of vectors that are common eigenvectors of $B$ and $A$, and that the eigenvalues of $B$ are $n-k-1,-1-\lambda_2,\dots,-1-\lambda_n$.

### 3 Responses to 403 – HW 4 – Algebraic graph theory

1. […] 1. Matoušek’s lecture 21 (continued). Algebraic graph theory. Homework 4, due May […]

2. andrescaicedo says:

I’ve slightly changed the phrasing of question 2: Rather than asking to show that $A$ and $B$ have the same eigenvectors, I am now asking the weaker result that there is a basis consisting of common eigenvectors. The result as stated originally (which is how it is stated in the Godsil-Royle book) is false:

Consider the graph $G$ on vertex set $\{1,2,3,4\}$ and only two edges: $1$ connected to $2$, and $3$ connected to $4$. The vector $\left(\begin{array}{c}1\\1\\{0}\\{0}\end{array}\right)$ is an eigenvector of $A$, but not of $B$.

• andrescaicedo says:

As an extra credit problem (to be turned in with the rest of the homework), check that if $G$ and $\bar G$ are both connected, then we can recover the stronger conclusion: $A$ and $B$ have exactly the same eigenvectors.