SCHWEITZER 1977 Problem 5

Suppose that the automorphism group of the finite undirected graph $X=(P, E)$ is isomorphic to the quaternion group (of order $8$ ). Prove that the adjacency matrix of $X$ has an eigenvalue of multiplicity at least $4$ .

( $P= \{ 1,2,\ldots, n \}$ is the set of vertices of the graph $X$ . The set of edges $E$ is a subset of the set of all unordered pairs of elements of $P$ . The group of automorphisms of $X$ consists of those permutations of $P$ that map edges to edges. The adjacency matrix $M=[m_{ij}]$ is the $n \times n$ matrix defined by $m_{ij}=1$ if $\{ i,j \} \in E$ and $m_{i,j}=0$ otherwise.)

L. Babai