(a) A simple connected undirected graph is regular if every vertex of the graph has the same degree. LetAGdenote the adjacency matrix of a simple undi- rected graphG. Determine in terms of the eigenvalues ofAGa necessary and sufficient condition forGto be both bipartite and regular. Give a detail proof of your claim.

b ) Let AG 6 {0,1}"xn and Ag G {0, 1}\"x" denote adjacency matrices of two simple directed graphs G and H. Consider the following relaxation for graph isomorphism (PTAHP) = AG subject to FTP = In, Prove that if the relaxation above admits at least one solution then G and H have the same number of closed walks of length k for every integer k