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 .
[…] 1. Matoušek’s lecture 21 (continued). Algebraic graph theory. Homework 4, due May […]
I’ve slightly changed the phrasing of question 2: Rather than asking to show that and 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 on vertex set and only two edges: connected to , and connected to . The vector is an eigenvector of , but not of .
As an extra credit problem (to be turned in with the rest of the homework), check that if and are both connected, then we can recover the stronger conclusion: and have exactly the same eigenvectors.