#2: Let G be the graph with vertex set Z_2^n( the same as the n-cube) and with edge set defined as follows: {u, v} is an edge of G if u and v differ in exactly two coordinates (i.e., if ω( u, v) = 2). What are the eigenvalues of G?
#4: Let r, s ≥ 1. The complete bipartite graphK rs has vertices u1,u2...,ur , v 1, v 2, ... vs, with one edge between each u i and v j (so rs edges in all). (a) By purely combinatorial reasoning, compute the number of closed walks of length l in K rs . (b) Deduce from (a) the eigenvalues of K rs .
#5: Let H n be the complete bipartite graph K nn with n vertex-disjoint edges removed. Thus H n has 2n vertices and n( n - 1) edges, each of degree (number of incident edges) n - 1. Show that the eigenvalues of G are ± 1 (n - 1 times each) and ± (n - 1) (once each).
#9: Let G be a (finite) graph with vertices v1,...,vp and eigenvalues λ1,...λp . We know that for any i, j there are real numbers c1(i,j),...cp(i,j) such that for all l ≥ 1, (a) Show that ck(i, i) ≥ 0. (b) Show that if i ≠ j then we can have c k (i, j) < 0. (The simplest possible example will work.)