Solution to the Clebsch puzzle

Here is the solution to the puzzle about the Clebsch graph I posed at the weekend. Since Gordon and Tony (and probably others) have already solved it, I am giving you my solution now.

The puzzle was:

Suppose we delete the edges of two edge-disjoint Clebsch graphs from K₁₆. What can we say about the graph formed by the remaining edges?

It is known that the edge set of the complete graph can be partitioned into three Clebsch graphs. As observed by Greenwood and Gleason, since Clebsch is triangle-free, this shows that we can colour the edges of the complete graph with three colours so that no monochromatic triangles are created, thereby demonstrating that the corresponding Ramsey number is 17 (it is not hard to show that with 17 vertices we necessarily create a monochromatic triangle). So, if you said, “The graph could be a Clebsch graph”, you would not be wrong …

But the answer to the puzzle is that the complement of two copies of the Clebsch graph is necessarily a third copy of the Clebsch graph!

Here is why.

By standard techniques for strongly regular graphs, the eigenvalues of the adjacency matrix of the Clebsch graph are 5 (multiplicity 1, corresponding to the all-1 vector), 1 (multiplicity 10), and −3 (multiplicity 5). Suppose we have two edge-disjoint Clebsch graphs, with adjacency matrices A and B, and let C be the adjacency matrix of the graph formed by the remaining edges, so that A+B+C+I = J, where I is the identity matrix and J the all-1 matrix.

Now each of A and B has a 10-dimensional space of eigenvectors with eigenvalue 1, inside the 15-dimensional space orthogonal to the all-1 vector. These must intersect in a 5-dimensional space. Since the eigenvalues of I and J on this space are 1 and 0 respectively, the matrix equation shows that the vectors in the space are eigenvectors of C with eigenvalue −3. So C has eigenvalue −3 with multiplicity 5, in addition to the simple eigenvalue 5 corresponding to the all-1 vector.

Let r₁,…,r₁₀ be the remaining eigenvalues of C. Since the trace of C is 0 and the trace of C² is 80 (twice the number of edges), we see that

r₁+…+r₁₀ = 10,
r₁²+…+r₁₀² = 10.

So we have

(r₁−1)²+…+(r₁₀−1)² = 0.

So r₁ = … = r₁₀ = 1.

Thus the graph C has the same eigenvalues as the Clebsch graph, and so is also strongly regular (16,5,0,2). But it is easy to see that the Clebsch graph is characterised by its parameters. (The valency is 5, and any vertex not joined to a fixed vertex * is joined to two neighbours of *; there are 10 such vertices and 10 pairs from 5, so this is a bijection. Now the induced subgraph on non-neighbours of * has valency 3, and two adjacent non-neighbours must be disjoint since otherwise a triangle is created; since there are only three pairs disjoint from a given one, everything is forced.)