MathDB

Suppose that the automorphism group of the finite undirected graph X\equal{}(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\equal{} \{ 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\equal{}[m_{ij}] is the

n \times n

matrix defined by m_{ij}\equal{}1 if

\{ i,j \} \in E

and m_{i,j}\equal{}0 otherwise.) L. Babai

Problem Statement