In the previous post, we introduced strongly regular graphs, with a particular interest in whether an srg(99,14,1,2) could exist. In this post, we’ll look at some properties such a graph G – or various subgraphs G’ – would have to satisfy.

(throughout, we’ll use G to refer to any Conway 99-graph, and use ‘subgraph’ to describe graphs obtained by vertex deletions only – sometimes called proper or induced subgraphs – rather than the more general concept which allows edge deletions too.)

The degree of every vertex is necessarily 14

First, then, we should make good on the promise to prove that the degree parameter k is 14, since Conway’s formulation of the problem only specifies the number of vertices and the mutual neighbour parameters λ=1, μ=2.

For this, we’ll use a double counting argument – expressing the same number in two different ways, and equating those expressions. For this, pick any vertex of G and call it vertex 0. Then as G is assumed to be regular, 0 has k neighbours, wlog vertices 1…k. Let A be the set of vertices 1…k, and B be the set of vertices k+1…98 (i.e. all the vertices apart from 0 and its neighbours). The quantity we will count is the number of edges between vertices in A and vertices in B.

• First, consider any vertex i in A. As a neighbour of vertex 0, they must have precisely one neighbour in common; since all the neighbours of 0 are in A, so there must be an edge from i to precisely one other i’ in A. Apart from the edge linking i to 0, all other edges starting at A must be to vertices in B. For vertex i to have degree k, there must therefore be k-2 edges from vertex i to B. Our choice of vertex i was arbitrary from A, which contains k vertices; so in total there are k(k-2) edges from A to B.
• Conversely, consider any vertex j in B. j is not a neighbour of vertex 0, so they must have 2 mutual neighbours; necessarily those are vertices of A (else they don’t neighbour 0 either). Thus each of our 98-k vertices k+1…98 contributes 2 edges from B to A, for a total of 2(99-k-1) = 196 – 2k.
• Since the edges from A to B are precisely the edges from B to A, we have equality: k(k-2) = 196 – 2k. So k^2 = 196, which for positive k forces k=14 as claimed.

The neighbourhood of each vertex is a seven-bladed fan

Implicit in the above was a description of the neighbourhood of any vertex v of G – that is, the subgraph N(v) consisting of that vertex and all of its neighbours. Let 0 be an arbitrary vertex and pick any neighbouring vertex, calling that vertex 1. Then as 0 and 1 are neighbours, they have precisely one mutual neighbour; wlog vertex 2. This gives us a ‘fanblade’ consisting of vertices 0,1,2: neither vertex 1 nor 2 can have any other neighbours in N(0). We can repeat this process to introduce the vertices in pairs 3-4, 5-6, 7-8, 9-10, 11-12 and 13-14. Thus N(0) is a seven-bladed fan:

Up to labelling, N(v) for any v in G is of this form.

Eigenvalue constraints

We will not prove these results here, but any strongly regular graph has precisely 3 eigenvalues whose values and multiplicities are determined by v,k,λ,μ. For our parameters, the eigenvalues of G are therefore:

• 14, with multiplicity 1
• 3, with multiplicity 54
• -4, with multiplicity 44

The interlacing theorem therefore gives strong requirements on the eigenvalues of sufficiently large subgraphs G’ of G. Recall that if A is an n-vertex graph with eigenvalues a_1…a_n and B is obtained from A by deleting a vertex, then the eigenvalues b_1…b_(n-1) of B interlace with the eigenvalues of A:

For G we have a_1 = a_2 = …. = a_44 = -4, a_45 = a_46 = … = a_98 = 3, a_99 = 14. So if G’ is a 98 vertex subgraph of G, almost all of its eigenvalues are known too: b_1 through b_43 must be -4, and b_45 through b_97 must be 3. The only freedom is in b_44, which can take values in [-4,3]; and b_98, which can take values in [3,14].

Iterating this process, we arrive at the following corollaries:

Let G’ be any subgraph of G. Then:

• e≥ -4 for any eigenvalue e of G’
• e≤ 14 for any eigenvalue e of G’
• If e>3 is an eigenvalue of G’, then e has multiplicity 1
• There cannot be two eigenvalues e,e’ of G’ such that e’ > e > 3.

Let G’ be a subgraph of G with n vertices. Then:

• If n ≥ 56, then n-55 of the eigenvalues of G’ must take the value -4
• If n ≥ 46, then n-45 of the eigenvalues of G’ must take the value 3

Subgraph compatibility with strong regularity

Let a,b be vertices of a subgraph G of G’. If a and b are neighbours in G’, then they are neighbours in G, so there must exist precisely one c in G adjacent to both a and b. If a and b are not neighbours in G’, then they are not neighbours in G either (by our notion of subgraph); so there must exist precisely two vertices d,e in G adjacent to both a and b. However, these vertices c,d,e need not feature in G’ – their absence is not reason to discard G’ as a potential subgraph of G.

Conversely, if a proposed G’ has too many mutual neighbours, then this can never be ‘fixed’ by adding more vertices, so we can rule out such a subgraph. Thus we have:

Let G’ be a subgraph of G. Then:

• If a and b are adjacent vertices in G’, then they have at most one mutual neighbour in G’
• If a and b are non-adjacent vertices of G’, then they have at most two mutual neighbours in G’

However, these mutual neighbours must eventually be introduced, and so we can additionally rule out candidate subgraphs where we have missed this opportunity:

Let G’ be a subgraph of G containing a vertex a and all of its neighbours in G, a_1…a_14. Then:

• Each a_i must neighbour precisely one other a_j
• For any b in G’ not amongst the a_i (or a itself), b must be a neighbour of precisely two of the a_i

Finally, we have the trivial observation that the regularity condition also restricts G’:

Let a be a vertex of a subgraph G’ of G. Then a has degree at most 14.

In the next post we’ll attempt to ‘grow’ our way towards G from a subgraph – we won’t get far enough to make use of our eigenvalue constraints, but we are able to enumerate the possibilities for the subgraph consisting of two adjacent vertices and their combined neighbourhoods. Before that, though, I wanted to note in passing some other properties of the Conway graph that I found during my research, although I don’t know how I would test for them…

Group-theoretic restrictions

• From “On the (99,14,1,2) strongly regular graph” (pp. 342-355 of this collection), if G exists, it does not have an automorphism of order 11, which implies that the automorphism group cannot be transitive.
• Example 3.2 of this paper gives the critical group of G.