Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2015/ii/paper-1/14i/c/solution

Count edges from the neighbours of a fixed vertex to its nonneighbours. Each neighbour contributes such edges, and each nonneighbour receives . With ,
The graph is incomplete, so there are nonadjacent vertices and . Substituting into the eigenvalue multiplicity formula gives a multiplicity difference of . This must be an integer. As , is rational and hence an integer; it is positive and odd. Moreover and , so reducing modulo gives . Thus . The value gives , impossible here; the other two give and . Consequently . This is a necessity argument, not a claim that integrality alone constructs either graph.

New to topics? Read the docs here!