This set is due Thursday, May 15, at 11am.
1. (Norman Biggs, Algebraic Graph Theory, Proposition 2.3) Let be a (finite, simple) graph with vertices, and let be its adjacency matrix. Suppose that the characteristic polynomial of is . Verify that:
- is the number of edges in .
- is twice the number of triangles in .
2. (Chris Godsil, Gordon F. Royle, Algebraic Graph Theory, Theorem 8.5.1) Let be a finite simple graph on vertices that is -regular, that is, such that each vertex has degree . Suppose has vertices and is its adjacency matrix.
- Verify that is an eigenvalue of .
- Let be the other eigenvalues of . Let denote the complementary graph to : This graph has the same vertices, but two vertices are joined by an edge iff they are not joined by an edge in . Let be the adjacency matrix of . Show that there is a basis of consisting of vectors that are common eigenvectors of and , and that the eigenvalues of are .