Past exam of the mathematics course of the University of Cambridge 2015 ii Paper 1 14I c Solution Created 2026-09-24 Updated 2026-10-06
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.