Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 4 16H Solution 2026-10-05
For the Petersen graph, each vertex has three neighbours, adjacent vertices have no common neighbour, and distinct nonadjacent vertices have exactly one common neighbour. The entries of count length-two walks, so diagonal entries are three, adjacent entries zero, and other off-diagonal entries one. HenceThe connected graph has the simple eigenvalue three with eigenvector . On its orthogonal complement , so the remaining eigenvalues satisfy and are one or minus two. If their multiplicities are , then and . Thus
The Petersen graph has ten vertices, fifteen edges, and girth five. One way to verify the girth is its description by the two-element subsets of a five-element set, with adjacency meaning disjointness. A triangle would require three pairwise disjoint two-element subsets, which is impossible. Two distinct vertices have at most one common neighbor: the only possible common neighbor is a two-element subset of the complement of their union. Therefore a four-cycle is impossible. A five-cycle exists in its standard pentagon drawing.
If it were a planar graph, part (i) would give , a contradiction. Thus the Petersen graph is nonplanar. The held source has blank space where its drawing is mentioned; the named graph determines this argument without that missing illustration.