Strongly regular graphs with parameters ( 85 , 14 , 3 , 2 ) (85,14,3,2) do not exist Sergey Shpectorov, Tianxiao Zhao Abstract We investigate the second smallest unresolved feasible set of parameters of strongly regular graphs, ( v , k , λ , μ ) = ( 85 , 14 , 3 , 2 ) (v,k,\lambda,\mu)=(85,14,3,2) . Using the classification of cubic graphs of small degree, we restrict possible local structure of such a graph G G . After that, we exhaustively enumerate possible neighbourhoods of a maximal 3 3 -clique of G G and check them against a variety of conditions, including the combinatorial ones, coming from λ = 3 \lambda=3 and μ = 2 \mu=2 , as well as the linear algebra ones, utilising the Euclidean representation of G G . These conditions yield contradiction in all cases, and hence, no srg ⁡ ( 85 , 14 , 3 , 2 ) \mathrm{srg}(85,14,3,2) exists. Keywords: strongly regular graph, euclidean representation 1 Introduction In this paper we consider undirected graphs without loops and multiple edges. A strongly regular graph is a connected regular graph G such that the number of common neighbours of two distinct vertices u,v\in G depends only on whether or not u and v are adjacent. Four parameters are used to describe the properties of a strongly regular graph G : the number of vertices, v , the valency, k , the number of neighbours of two adjacent vertices, \lambda , and the number of neighbours of two non-adjacent vertices, \mu . We will use the notation \mathrm{srg}(v,k,\lambda,\mu) for any strongly regular graphs with these parameters. The four parameters are not independent; in fact, they satisfy several feasibility conditions . Parameters satisfying these conditions are called feasible . Given a feasible parameter set (v,k,\lambda,\mu) , one can ask whether there is a strongly regular graph with such parameters, and if so, how many different \mathrm{srg}(v,k,\lambda,\mu) are there up to isomorphism. The answer to this question varies for different parameter sets. For some feasible parameters, the corresponding strongly regular graphs exist and occasionally there may be a significant number of non-isomorphic graphs with the same parameters. For other feasible parameter sets, no \mathrm{srg}(v,k,\lambda,\mu) exist. In other words, feasibility of parameters does not guarantee the existence of a strongly regular graph. All feasible parameter sets with v\leq 1300 are listed in an online catalogue [ 1 ] maintained by Brouwer. For each parameter set, the catalogue lists the key properties of the graph and additional comments describing what is currently known about this case. We note that the complement graph of a strongly regular graph is also strongly regular, as long as it is connected. Hence, strongly regular graphs and their parameter sets normally come in pairs. For v\leq 100 , there are only nine unresolved cases, where it is not known whether the strongly regular graphs with the given feasible parameter set exist. The smallest case is for v=69 and the next three unresolved cases have v=85 . In this paper, we resolve one of these three cases. Namely, we prove the following result. Theorem 1.1 . There is no strongly regular graph with parameters (85,14,3,2) . The complementary array is (85,70,57,60) and, clearly, such strongly regular graphs also cannot exist. Previous knowledge about \mathrm{srg}(85,14,3,2) was very limited. Paduchikh in [ 10 ] investigated how automorphisms of prime order could act on such a graph and what would be the fixed subgraph of such an automorphism. There are several ingredients to our proof of Theorem 1.1 . First of all, each local subgraph G_{1}(x) (i.e., subgraph induced on the neighbourhood of a vertex x ) of G=\mathrm{srg}(85,14,3,2) is a cubic graph on 14 vertices. Connected cubic graphs on at most 14 vertices have been completely enumerated, see e.g., [ 4 , 3 ] . Going through the list, we determine all possible local graphs, using the additional strong condition that two non-adjacent vertices in the local graph can have at most one common neighbour. This holds since \mu=2 . The final list of possible local graphs, called good graphs below, includes 36 connected graphs and 3 disconnected graphs, consisting of two components, a 4 -clique and a connected cubic graph on 10 vertices. One immediate corollary of this is that G contains maximal 3 -cliques. We select one such clique, Q=\{x,y,z\} , and we do in the computer algebra system GAP [ 6 ] a complete enumeration of possible subgraphs arising on the set T of vertices adjacent to Q . Since |T|=30 , this enumeration is huge and it cannot be done carelessly. We represent T as a union of three 12 -vertex segments , S_{x}=G_{1}(x)\setminus Q , S_{y}=G_{1}(y)\setminus Q and S_{z}=G_{1}(z)\setminus Q , corresponding to the three vertices in Q . Each segment is a subgraph of a local graph, and so possible segments can be enumerated up to isomorphism, giving us a total of 478 possible segments. Within T , two segments intersect in a 2 -vertex set called a handle (see Section 4 for all relevant definitions and discussion). A handle can be an edge or a non-edge and this leads to a compatibility condition for pairs of segments within T . We pre-compute the list of 86333 (ordered) pairs of compatible segments S_{x}\cup S_{y} joined at a handle, up to isomorphism. These pairs give us the cases into which we split the entire calculation. In each case, the calculation goes through four steps: • Step 1: Enumerating possible graph structures on S_{x}\cup S_{y} . • Step 2: Gluing in a third segment S_{z} in all possible compatible ways and enumerating all graph structures on T=S_{x}\cup S_{y}\cup S_{z} . A great majority of cases are eliminated at this step. • Step 3: For each T not eliminated at Step 2, enumerate all possible sets C of additional neighbours of a fixed vertex t\in X=S_{y}\cap S_{z} . • Step 4: Enumerate all possible graph structures on C and hence on the entire T\cup C , achieving elimination in all cases. In addition to purely combinatorial arguments involving the parameters of G , we rely for elimination on the linear algebra conditions coming from the Euclidean representation of G . It is well-known that a strongly regular graph can be realised as a set of unit vectors in an eigenspace of its adjacency matrix. The value of the dot product of two unit vectors corresponding to vertices u and v is given in the so-called cosine sequence of G , and it depends only on the distance between u and v in G . The eigenvalues of the adjacency matrix of G and their multiplicities can be computed from the parameters of G . For G=\mathrm{srg}(85,14,3,2) , the adjacency matrix has eigenvalues k=14 , 4 , and -3 , with respective multiplicities 1 , 34 , and 50 . For our calculation, we selected the unit vector realisation in the eigenspace E of dimension 34 corresponding to the eigenvalue 4 . The cosine sequence for this Euclidean representation is w_{0}=1 , w_{1}=\frac{2}{7} , and w_{2}=-\frac{1}{14} . That is, adjacent vertices lead to the dot product value \frac{2}{7} and the non-adjacent vertices lead to the value -\frac{1}{14} . Once we know all edges on a subset X of G , such as, say, T or T\cup C (or a subset of these sets), we can create the Gram matrix corresponding to X . Since the dot product is positive definite on E , the Gram matrix of every subset of G must be semi-positive definite, i.e., it cannot have negative eigenvalues. The strength of this linear algebra condition grows with the size of the subset X we consider. For example, none of the possible sets S_{x}\cup S_{y} (of cardinality 22 ) is eliminated by this condition. However, for T=S_{x}\cup S_{y}\cup S_{z} (whose size is 30 ), this condition is very powerful and it eliminates a large majority of all possible configurations of edges, depending on the specific case. Clearly, we want to eliminate each configuration as early as possible, so we build up T vertex by vertex and check semi-positive definiteness along the way. Also, note that the rank of the Gram matrix cannot exceed \dim E=34 . Hence, at Step 4, where the size of T\cup C grows to 38>34 , the rank consideration can be applied with a devastating effect, eventually eliminating all configurations. While the overall idea of our four-step enumeration looks quite simple and straightforward, it was found as a result of much experimentation. Even with our approach above, the total enumeration involves an astronomical number of possible configurations, and so the enumeration would not have been possible without a very effective code in GAP. Because of this, we also devote much attention below to the exact algorithmic details, including some key data structures and even some code. We do not include the entire code we created and used, due to its length, but it is available on GitHub [ 11 ] . Finally, let us describe the contents of the paper section by section. In Section 2, we provide the background information on strongly regular graphs and their Euclidean representations. In Section 3, we identify the possible local subgraphs of G=\mathrm{srg}(85,14,3,2) , starting from the known lists of cubic graphs of small size. In Section 4, we discuss the concepts of segments and handles, which are the building blocks for our set T . We determine the complete list of possible segments and classify them according to their type. Gluing of segments over the common handles is described in Section 5, where we develop the group-theoretic methods allowing us to avoid repetitions. This leads to finding the list of 86333 pairs of segments glued over a common handle, which constitute the cases into which we split the calculation. We also describe in this section the main idea of our approach, focussing on the set T=S_{x}\cup S_{y}\cup S_{z} . Not every edge in T is contained in one of the three segments. Hence, we study the edges that cut across segments, and we show that such edges form a matching between the subsets in the two segments, called the cores . This results informs the enumeration method we select, using enumeration trees . In Section 6, we provide some data and algorithmic details: ordering of the vertices in a segment and the resulting quad type, which accomplishes a finer classification of segments. We also discuss in this section the overall organisation of Steps 1 and 2. By the end of Step 2, we have already eliminated a large majority of all cases. However, even a tiny percentage of survivors, leads to a very large number of cases, for which we need to do further steps. In Section 7, we describe properties of the additional vertices we add, namely to the additional neighbours of a vertex t\in X=S_{y}\cap S_{z} . We identify each additional vertex with its set of neighbours in T , discuss compatibility of additional vertices, and provide the details of the recursive enumeration we do at Step 3. In Section 8, we similarly discuss the details of Step 4, where we have in hand a complete set C of neighbours of t and we enumerate the possible edges on C and achieve the final elimination. In Section 9, we describe an additional idea, based on the careful selection of the 3 -clique Q=\{x,y,x\} , identifying our set T . This additional idea leads to a significant overall reduction in the number of cases we need to consider, and it also leads to a more simple algorithm. Section 10 contains brief concluding remarks. The paper has three appendices. Appendix A describes the enumeration trees we use at Steps 1 and 2. Appendix B deals with the details of the LDLT algorithm we use to verify semi-positive definiteness as we add vertices one by one. Finally, in Appendix C we describe and justify the method we use to compute projections to E , which we use extensively at Steps 3 and 4. The enumeration was carried out in parallel on 96 cores in four servers in the School of Mathematics at the University of Birmingham. We especially thank David Craven, who manages these servers and who tolerated our 96 copies of GAP, running continuously from November 2023 till January 2025. 2 Preliminaries 2.1 Graphs In this section we will briefly introduce some background concepts and facts. By a graph we mean a simple graph, without loops or multiple edges. We will identify a graph G with its vertex set and will use E(G) to denote its edge set. We will only deal with finite graphs, i.e., |G| (and hence also |E(G)| ) will be finite. We call v=|G| the order of the graph G . For x,y\in G , we write x\sim y (respectively, x\not\sim y ) to indicate that x and y are adjacent (respectively, non-adjacent). A path from x to y is a sequence p=(x_{0},x_{1},\ldots,x_{n}) of vertices, where x=x_{0} , y=x_{n} and x_{i-1} is adjacent to x_{i} for all i=1,2,\ldots,n . We call n the length of the path p . We will typically assume that the graph is connected, that is, any two vertices of it are connected by a path. Length of the shortest path between x and y is known as the distance between x and y . The largest distance between vertices of G is called the diameter of G . For i\geq 1 , by G_{i}(x) we mean the set of vertices of G at distance i from x . In particular, G_{1}(x) is the set of neighbours of x in G . Recall that G is called k - regular if |G_{1}(x)|=k for every x\in V(G) . Then we call k the degree of the regular graph G . For X\subset G , we will similarly identify the subset X with the induced subgraph on X . This is the subgraph that includes all edges with both ends in X . In particular, we will often refer to G_{1}(x) as the local subgraph of G . Consider a graph G=\left\{u_{1},u_{2},\dots,u_{v}\right\} . The adjacency matrix A=A(G) is the square matrix of size v , whose entries satisfy: a_{ij}=\left\{\begin{array}[]{rl}1,&\text{if }u_{i}\sim u_{j},\\ 0,&\text{if }u_{i}\not\sim u_{j}.\end{array}\right. The spectrum of the graph G is the spectrum of its adjacency matrix A . In other words, if A has eigenvalues \lambda_{1},\lambda_{2},\dots,\lambda_{s} with multiplicities m_{1},m_{2},\dots,m_{s} , then the multiset \operatorname{Spec}(G)=\{\lambda_{1}^{m_{1}},\lambda_{2}^{m_{2}},\dots,\lambda_{s}^{m_{s}}\} is the spectrum. Note that A is symmetric and hence all its eigenvalues \lambda_{i} are real. Furthermore, A is semisimple (diagonalisable), that is, \mathbb{R}^{v} decomposes as the direct sum of the eigenspaces of A and hence \sum_{i=1}^{s}m_{i}=v . We also note the following standard fact about symmetric real matrices. Lemma 2.1 . Distinct eigenspaces of A=A(G) are orthogonal with respect to the dot product on \mathbb{R}^{v} . Therefore, the above decomposition of \mathbb{R}^{v} as a direct sum of eigenspaces of A is orthogonal. If G is k -regular then each row of A has exactly k ones. Hence k is an eigenvalue of A . Furthermore, if G is connected then k has multiplicity 1. The corresponding eigenspace is spanned by the all-one vector. We conclude this section with the following definition. An automorphism of a graph G is a permutation of G that preserves adjacency. We denote by \operatorname{Aut}(G) the group of all automorphisms of G . 2.2 Strongly regular graphs A strongly regular graph is a connected regular graph, for which there exist non-negative integers \lambda and \mu , such that any two adjacent vertices have exactly \lambda common neighbours and any two non-adjacent vertices have exactly \mu common neighbours. We will write \mathrm{srg}(v,k,\lambda,\mu) for a strongly regular graph on v vertices, of degree k , and with parameters \lambda and \mu , as above. We follow [ 8 ] for the basic results on strongly regular graphs. Theorem 2.2 . For an \mathrm{srg}(v,k,\lambda,\mu) , let A be its adjacency matrix, I be the identity matrix and J be the all-one matrix, both of the same order as A . Then the following relations hold: AJ=kJ\mbox{ and }A^{2}+(\mu-\lambda)A+(\mu-k)I=\mu J. As an application of these equations, we have the following theorem. Theorem 2.3 . If G=\mathrm{srg}(v,k,\lambda,\mu) then its spectrum is \left\{k^{1},r^{f},s^{g}\right\} , where r,s,f,g are given by: \displaystyle r \displaystyle=\tfrac{1}{2}\left(\lambda-\mu+\sqrt{(\lambda-\mu)^{2}+4(k-\mu)}\right), \displaystyle s \displaystyle=\tfrac{1}{2}\left(\lambda-\mu-\sqrt{(\lambda-\mu)^{2}+4(k-\mu)}\right), \displaystyle f \displaystyle=\tfrac{1}{2}\left(v-1-\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^{2}+4(k-\mu)}}\right), \displaystyle g \displaystyle=\tfrac{1}{2}\left(v-1+\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^{2}+4(k-\mu)}}\right). Let us now see what this translates to for a possible \mathrm{srg}(85,14,3,2) . Corollary 2.4 . If G=\mathrm{srg}(85,14,3,2) then A(G) has eigenvalues 14 , 4 , and -3 with multiplicities 1 , 34 , and 50 , respectively. This is obtained by plugging the values of (v,k,\lambda,\mu)=(85,14,3,2) into the formulae from Theorem 2.3 . 2.3 Euclidean representation Now we introduce the Euclidean representation of a strongly regular graph, which will be the main tool that we will use to eliminate cases in this project. The theory is mostly based on the book of Godsil [ 7 ] . There it is developed for arbitrary distance-regular graphs, so we adjust it for our case: strongly regular graphs are distance-regular graphs of diameter 2 . We also slightly alter the notation from the book. As above, let G=\left\{u_{1},u_{2},\dots,u_{v}\right\} be a strongly regular graph with parameters (v,k,\lambda,\mu) . We will identify G with the standard basis of U=\mathbb{R}^{v} . Recall that k , r and s are the eigenvalues of the adjacency matrix A=A(G) of G , of multiplicity 1 , f and g , respectively. It follows from Theorem 2.3 and the discussion around Lemma 2.1 that we have the following orthogonal decomposition: U=U_{k}\oplus U_{r}\oplus U_{s}, where U_{\theta} is the \theta -eigenspace of A for each \theta\in\{k,r,s\} . As we already mentioned, since G is connected, the 1 -dimensional eigenspace U_{k} is spanned by the all-one vector. For \theta\in\{k,r,s\} , consider the orthogonal projection p_{\theta}:U\rightarrow U_{\theta} . Then we have the following result (see Lemma 1.2 in Chapter 13 of [ 7 ] ). Theorem 2.5 . For u_{i},u_{j}\in V(G) , the value of p_{\theta}(u_{i})\cdot p_{\theta}(u_{j}) depends only on the distance between u_{i} and u_{j} . We will represent the vertices of G by their images under p_{\theta} , but scaled to have length 1 . That is, the Euclidean representation of G with respect to \theta represents every vertex u_{i} by the unit vector e_{i}:=\frac{1}{|p_{\theta}(u_{i})|}p_{\theta}(u_{i}) from the subspace U_{\theta} . If the distance between u_{i} and u_{j} is m\in\{0,1,2\} then we have, by Theorem 2.5 , that w_{m}:=e_{i}\cdot e_{j}=\frac{p_{\theta}(u_{i})\cdot p_{\theta}(u_{j})}{|p_{\theta}(u_{i})||p_{\theta}(u_{j})|} is a function of m alone. The values w_{m} , m\in\{0,1,2\} , are known as the cosine sequence of G . We can furthermore claim the following exact formulae for the values of w_{m} . Theorem 2.6 ( [ 2 ] , Section 4.1B) . We have that w_{0}=1 , w_{1}=\frac{\theta}{k} and w_{2}=\frac{\theta^{2}-\lambda\theta-k}{k(k-\lambda-1)} . We now specialise this to the case of \mathrm{srg}(85,14,3,2) . First of all, we choose \theta=4 (c.f. Corollary 2.4 ), so that our representation is in the eigenspace E:=U_{4} of dimension 34 . From now on, this is our fixed choice. Corollary 2.7 . For G=\mathrm{srg}(85,14,3,2) and \theta=4 , the cosine sequence is w_{0}=1 , w_{1}=\frac{2}{7} and w_{2}=-\frac{1}{14} . Hence, when the vertices u_{i} and u_{j} are adjacent, we have that e_{i}\cdot e_{j}=\frac{2}{7} and, when u_{i} and u_{j} are non-adjacent, we have that e_{i}\cdot e_{j}=-\frac{1}{14} . Note that the unit vectors \{e_{1},e_{2},\ldots,e_{v}\} span E . Indeed, this follows from the fact that \{u_{1},u_{2},\ldots,u_{v}\} is a basis of U=\mathbb{R}^{v} . From this point on, G=\mathrm{srg}(85,14,3,2) and it is realised by the unit vectors e_{i} in the 34 -dimensional Euclidean space E as above. Our goal is to obtain a contradiction, showing non-existence of G , by considering various sets of vectors e_{i} . If X is such a set, then the Gram matrix corresponding to X must be semi-positive definite, i.e., it cannot have negative eigenvalues. This is because the dot product on E\subset U is positive definite. 3 Local structure of G Let us focus on the local subgraph G_{1}(x) of G , induced by the 14 neighbours of a vertex x\in G . Since \lambda=3 , the subgraph G_{1}(x) is cubic, i.e., of degree 3 . Connected cubic graphs on at most 14 have been enumerated, see e.g. [ 4 , 3 ] . The complete list of all these graphs can be found on the internet and examined via, say, the computer algebra system GAP [ 6 ] . Since at this point we cannot assume that the local subgraphs G_{1}(x) are connected, we should also add disconnected cubic graphs on 14 vertices, as unions of smaller connected cubic graphs. In total, there are, up to isomorphism, 509 connected cubic graphs on 14 vertices and 31 disconnected ones. Lemma 3.1 . Any two non-adjacent vertices y,z\in G_{1}(x) have at most one common neighbour in G_{1}(x) . Proof. Since \mu=2 , any two non-adjacent vertices y,z\in G_{1}(x) have two common neighbours in G . One of them is x , hence y and z have at most one common neighbour in G_{1}(x) . ∎ It turns out this simple lemma allows us to reduce significantly the number of possible graphs G_{1}(x) . Going through the list of all 540 cubic graphs on 14 vectices, we discover that only 39 of them, referred to in this paper as the good cubic graphs, satisfy the condition from Lemma 3.1 . Hence we have the following. Proposition 3.2 . The local subgraph G_{1}(x) , for x\in G , is isomorphic to one of the 39 good cubic graphs. Out of these graphs, 36 are connected and 3 are disconnected, namely, they are unions of a 4 -clique and a connected trivalent graph T_{i} of order 10 , i=1,2,3 , shown in Figure 1 . Note that T_{3} is the Petersen graph. (a) T_{1} (b) T_{2} (c) T_{3} Figure 1: Relevant cubic graphs of order 10 Our method later in the text is based on considering on a neighbourhood of a maximal 3 -clique in G . We can derive the existence of such maximal cliques from the enumeration above. Proposition 3.3 . Maximal 3 -cliques exist in G . Proof. For a vertex x\in G , maximal 3 -cliques containing x correspond to edges in G_{1}(x) not contained (within G_{1}(x) ) in a 3 -clique. Hence the existence of maximal 3 -cliques can be established by simply going through the list of 39 possible local graphs. ∎ Alternatively, it is easy to show that if y\in G_{1}(x) is not contained in a component of size 4 of G_{1}(x) then its local graph in G_{1}(x) is either a 3 -coclique or a union of an edge and an isolated vertex. Hence every such edge xy is contained in a maximal 3 -clique in G . We can formulate this as follows, specialising Proposition 3.3 . Proposition 3.4 . Every edge xy\in E(G) that is not contained in a 5 -clique, is contained in a maximal 3 -clique. In turn, this implies the following. Corollary 3.5 . Every vertex x\in G is contained in a maximal 3 -clique. 4 Segments and handles Let Q be a maximal 3 -clique in G . For each x\in Q , we have that yz=Q\setminus\{x\} is an edge in the local subgraph G_{1}(x) . We now focus on the remaining twelve vertices in G_{1}(x)\setminus yz . Since Q is maximal, the edge xy is not contained in a 3 -clique in the good cubic graph G_{1}(x) . Definition 4.1 . Suppose that H is a good cubic graph and yz is an edge in H not contained in a 3 -clique. Let S be the subgraph of H induced on H\setminus yz . We call S the segment corresponding to H and yz . Since yz is not contained in a 3 -clique, y and z have no common neighbours in H . Let y_{1} and y_{2} be the neighbours of y in H , other than z , and symmetrically, let z_{1} and z_{2} be the neighbours of z in H , other than y . Clearly, the pairs \{y_{1},y_{2}\} and \{z_{1},z_{2}\} are disjoint and contained in S . Definition 4.2 . We call the pairs \{y_{1},y_{2}\} and \{z_{1},z_{2}\} the handles of the segment S . We note that the segment is not just the graph S , but rather the triple consisting of S and the two handles \{y_{1},y_{2}\} and \{z_{1},z_{2}\} . Note also that while \{y_{1},y_{2},z_{1},z_{2}\} can be identified within S as the set of all vertices of S having only two neighbours, this set can potentially be split into a union of two handles in more than one way. Hence we need to view a segment as a triple, expressly indicating the handles. The order of the two handles is less important, but naturally, they are kept in a computer in some order. When we talk below about isomorphisms of segments S and S^{\prime} , we mean graph isomorphisms S\to S^{\prime} mapping the first and second handles of S to the first and second handles of S^{\prime} , respectively. We now turn to enumeration of segments. The good graph H can be easily recovered from its segment S . Indeed, we just need to add to S a new vertex y adjacent to the two vertices in the first handle \{y_{1},y_{2}\} and a second new vertex z adjacent to y and the vertices in the second handle \{z_{1},z_{2}\} . In particular, every segment S arises from a unique good cubic graph H . This allows for a very efficient enumeration of segments. We go through the list of the 39 good cubic graphs H . In each H , we determine the orbits under \operatorname{Aut}(H) on the set of ordered edges of H . Segments are isomorphic if and only if the come from the same orbit. Hence we obtain a complete list of segments by choosing one representative yz of each orbit and constructing the segment H\setminus yz . Before we report the results of this calculation, we need to discuss the types of handles and segments. A handle is a pair of vertices and, naturally, these two vertices can be adjacent or non-adjacent. Hence the handles are classified into edges and non-edges . Correspondingly, segments can be of four types depending on their first and second handle: (1) edge and edge; (2) edge and non-edge; (3) non-edge and edge; and (4) non-edge and non-edge. Clearly, for every segment of type (2), we obtain a segment of type (3) by switching the handles. Types (1) and (4) are invariant under this operation. Proposition 4.3 . There are in total 478 segments up to isomorphism. Among them there are 19 , 78 , 78 , 303 segments of types (1) , (2) , (3) , and (4) , respectively. We now introduce an additional structure on a segment. First, we need the following. Lemma 4.4 . Let S be a segment and Y=\{y_{1},y_{2}\} and Z=\{z_{1},z_{2}\} be its two handles. Then y_{i} and z_{j} are non-adjacent for all i,j=1,2 . Proof. Let H be the good cubic graph that S is obtained from, and yz be the edge removed from H . We assume that y_{1} and y_{2} are adjacent to y while z_{1} and z_{2} are adjacent to z . Now we can prove our claim: if y_{i} and z_{j} are adjacent then, in H , the vertices y_{i} and z have two common neighbours, y and z_{j} . This contradicts the condition from Lemma 3.1 that we imposed on good cubic graphs. ∎ We will need the following concept. Definition 4.5 . Let S be a segment and Y and Z be its handles. The core of S with respect to the handle Y is the set of vertices in S\setminus(Y\cup Z) that are not adjacent to a vertex of Y . The size of core depends on the type of the handle. Lemma 4.6 . If Y=\{y_{1},y_{2}\} is a handle of a segment S then y_{1} and y_{2} have no common neighbours in S . In particular, the core of S with respect to Y consists of six vertices, if Y is an edge, and the core consists of four vertices, if Y is a non-edge. Proof. Let H be the good cubic graph from which S was constructed by removing an edge yz . We assume that y is adjacent to y_{1} and y_{2} . Suppose that y_{1} and y_{2} have a common neighbour s in S . Then s is not adjacent to y and at the same time, s and y have two common neighbours, y_{1} and y_{2} . This is a contradiction since H is a good cubic graph. Thus, y_{1} and y_{2} have no joint neighbours in S . If Y is an edge then y_{1} has only one neighbour in S , other than y_{2} , and symmetrically, y_{2} has only one neighbour in S , other than y_{1} . Note that, by Lemma 4.4 , those neighbours are not in the second handle Z . Hence the core with respect to Y is obtained by removing from S the vertices in Y , Z and the two neighbours of Y , leaving six vertices in the core. If Y is a non-edge then each of y_{1} and y_{2} has two further neighbours in S and so the core is obtained in this case by removing Y , Z and the four neighbours of Y . Hence the core is of size four. ∎ This allows us to attach numerical labels to the segments; namely, each segment S will be labelled with a pair from \{6,4\}\times\{6,4\} , indicating the size of the cores with respect to the two handles. That is, type (1) above (edge and edge) becomes type (6,6) ; type (2) (edge and non-edge) becomes (6,4) ; type (3) (non-edge and edge) becomes type (4,6) ; and finally, type (4) (non-edge and non-edge) becomes type (4,4) . In fact, we can classify segments even more finely. For a segment S with handles X and Y , let the quadruple (n_{S},r_{S},l_{S},b_{S}) be defined as follows: n_{S}=|S_{0}\setminus(C_{X}\cup C_{Y})| , r_{S}=|C_{Y}\setminus C_{X}| , l_{S}=|C_{X}\setminus C_{Y}| , and b_{S}=|C_{X}\cap C_{Y}| , where S_{0}=S\setminus(X\cup Y) , C_{X} is the core of S with respect to X , and C_{Y} is the core of S with respect to Y . Clearly, n_{S}+r_{S}+l_{S}+b_{S}=|S_{0}|=8 , l_{S}+b_{S}=|C_{X}| , and r_{S}+b_{S}=|C_{Y}| . So this quadruple can serve as a finer invariant, and we call it the quad type of S . The table below shows the number of segments of each possible quad type. type quad type number of segments (6,6) (2,0,0,6) 0 (1,1,1,5) 5 (0,2,2,4) 14 (6,4) (2,0,2,4) 9 (1,1,3,3) 35 (0,2,4,2) 34 (4,4) (4,0,0,4) 4 (3,1,1,3) 23 (2,2,2,2) 146 (1,3,3,1) 102 (0,4,4,0) 28 Table 1: Quad types Note that there happens to be no segments of quad type (2,0,0,6) . Note also that we skipped the type (4,6) , which clearly has the dual (switching r_{S} and l_{S}) quad type distribution, compared to the type (6,4) . 5 Gluing segments The idea of our approach is to investigate the union of three local subgraphs G_{1}(x) , x\in Q , where Q is, as above, a maximal 3 -clique in G . Once we identify the graph induced on this set, we can produce the corresponding Gram matrix (since we assume that G is realised as a set of unit vectors in E ) and check this matrix for semi-positive definiteness hoping to eliminate in this way a great majority of all possibilities. Before we discuss how to glue local subgraphs together, let us make a slight adjustment. Namely, we will show that it suffices to glue together the three segments arising from Q . We will need the following result. Lemma 5.1 . For x\in G , we have that \sum_{y\in G_{1}(x)}y=4x . Proof. Let w=\sum_{y\in G_{1}(x)}y . Using Corollary 2.7 , we have that w\cdot w=14(1+3(\frac{2}{7})+10(-\frac{1}{14}))=14+12-10=16 and w\cdot x=x\cdot w=14(\frac{2}{7})=4 . In the first calculation, we used that every y\in G_{1}(x) has 3 neighbours and 10 non-neighbours in G_{1}(x) . Hence, for t=w-4x , we have that t\cdot t=(w-4x)\cdot(w-4x)=w\cdot w-4w\cdot x-4x\cdot w+16x\cdot x=16-16-16+16=0 . This means that t=0 , that is, w=4x , as claimed. ∎ As we already stated, we would like to recover the induced graph structure on the union \cup_{x\in Q}G_{1}(x) for a maximal 3 -clique Q . Clearly, this set is the union of Q and the three segments S_{x}:=G_{1}(x)\setminus Q , x\in Q . Let s_{x}:=\sum_{u\in S_{x}}u . Then we have the following vector equations. Lemma 5.2 . If Q=\{x,y,z\} then x=\frac{1}{10}(3s_{x}+s_{y}+s_{z}) , y=\frac{1}{10}(s_{x}+3s_{y}+s_{z}) , and z=\frac{1}{10}(s_{x}+s_{y}+3s_{z}) . Proof. By Lemma 5.1 , we have: \displaystyle s_{x}+y+z \displaystyle=4x \displaystyle s_{y}+x+z \displaystyle=4y \displaystyle s_{z}+x+y \displaystyle=4z Solving this linear system for x , y and z yields the claim. ∎ According to this lemma, the span of T:=\cup_{x\in Q}S_{x} includes Q and so the rank of the Gram matrix on T\cup Q is the same as the rank of the Gram matrix on T . We will therefore work with just T , ignoring the three vertices from Q . Next we discuss how we can recover the graph structure on T , which includes how the segments S_{x} , x\in Q , intersect, which edges T inherits from these segments, and which edges in T are extra. We start with the intersection of segments. Lemma 5.3 . For x,y\in Q , x\neq y , we have that Z:=S_{x}\cap S_{y} is a handle in both segments S_{x} and S_{y} . Proof. If z is the third vertex in Q then S_{x} is obtained from G_{1}(x) by removing the edge yz . Hence S_{x}\cap G_{1}(y) is a handle in S_{x} . It remains to see that S_{x}\cap G_{1}(y)=Z . On the one hand, Z=S_{x}\cap S_{y} is clearly contained in S_{x}\cap G_{1}(y) . On the other hand, the difference between S_{y} and G_{1}(y) is the edge xz . Both x and z are not contained in S_{x} , and hence, indeed, S_{x}\cap G_{1}(y)=S_{x}\cap S_{y}=Z . Symmetrically, Z is also a handle in S_{y} . ∎ Let us now fix the notation we will use in the remainder of the paper. Let Q=\{x,y,z\} and we set Z:=S_{x}\cap S_{y} , as above, and symmetrically, Y:=S_{x}\cap S_{z} and X:=S_{y}\cap S_{z} . This is shown in Figure 2 . Figure 2: The composition of T Our next result concerns the additional edges on S_{x}\cup S_{y} , or equally, any other union of two segments above. Recall from Section 4 the concept of the core of a segment with respect to a handle. Lemma 5.4 . Let C_{x}\subset S_{x} be the core of S_{x} with respect to Z=S_{x}\cap S_{y} and, symmetrically, let C_{y}\subset S_{y} be the core of S_{y} with respect to Z . Then every edge within S_{x}\cup S_{y} , that is not fully contained in S_{x} or S_{y} , connects a vertex from C_{x} with a vertex from C_{y} . Furthermore, such edges form a matching between C_{x} and C_{y} . Proof. Let u\in S_{x} . If u\in Z then every edge from u to a vertex of S_{y} is contained in S_{y} . If u is contained in the second handle, Y , of S_{x} then u and y already have \mu=2 common neighbours, namely, x and z , and so u has no neighbours in S_{y} . Similarly, if v\in S_{x}\setminus(Y\cup Z) but v is adjacent to a vertex z_{i} in Z then the common neighbours of u and y are x and z_{i} , and so again u has no further neighbours in S_{y} . Hence only the vertices from C_{x} can have further neighbours in S_{y} . Symmetrically, only vertices from C_{y} can have further edges in S_{x} . We have shown that the edges on S_{x}\cup S_{y} that are not fully in S_{x} or S_{y} connect C_{x} with C_{y} . Now let u\in C_{x} . Then x is a common neighbour of v and y . Since \mu=2 and since u is not adjacent to Z , it must have exactly one neighbour in S_{y} , and by the above, this unique neighbour is in C_{y} . Thus, every vertex in C_{x} has a unique neighbour in C_{y} and, symmetrically, every vertex of C_{y} has a unique neighbour in C_{x} ; that is, we have a matching between C_{x} and C_{y} , as claimed. ∎ Needless to say, we have similar matchings between the corresponding cores in S_{x} and S_{z} and in S_{y} and S_{z} . The process of forming T=S_{x}\cup S_{y}\cup S_{z} consists of several steps. We first glue together possible segments S_{x} and S_{y} by identifying corresponding handles, which become Z=S_{x}\cap S_{y} . Then we select and add a matching between the cores of S_{x} and S_{y} with respect to Z . Clearly, the segments we identify must be of the same type (edges or non-edges) and then the two cores do indeed have the same size and matchings are possible. We note that matchings between two sets of size m are in a natural correspondence with the elements of the symmetric group S_{m} , and so we have |S_{6}|=720 possible matchings if Z is an edge, and |S_{4}|=24 possible matchings if Z is a non-edge. At this point, after choosing a particular matching, we already known the induced graph on S_{x}\cup S_{y} and so we can write the Gram matrix corresponding to the set of unit vectors S_{x}\cup S_{y} in E . This could, in principle, lead to elimination of some configurations due to negative eigenvalues of their Gram matrices. However, as we discovered computationally, all double unions survive this criterion, and this is why we are forced to consider a larger triple union of segments. Hence, the next step is to glue in a third possible segment S_{z} by identifying its two handles with the remaining unmatched handles in S_{x} and S_{y} . This is followed by a selection of matchings between the cores in S_{x} and S_{z} with respect to Y=S_{x}\cap S_{z} and between the cores in S_{y} and S_{z} with respect to X=S_{y}\cap S_{z} . This completes forming of the induced graph on T and so the whole Gram matrix on T can be formed and checked for negative eigenvalues. Since |T|=30 is close to the dimension 34 of the ambient Euclidean space E , this check is now quite powerful and eliminates a great majority of cases. There are, of course, a lot of technical details concerning this process, which we will provide later. In the remainder of this section we discuss gluing two graphs over a common subgraph. Definition 5.5 . A gluing of graphs A and B over isomorphic subgraphs H_{A}\subseteq A and H_{B}\subseteq B is an isomorphism \phi:H_{A}\to H_{B} . A gluing produces a new graph by taking the union of A and B and, furthermore, identifying every vertex h of H_{A} with the corresponding vertex \phi(h) of H_{B} . Hence H_{A} and H_{B} merge into the intersection H=A\cap B . Note that the edges of the glued graph all come from the edges of A and B . Moreover, since \phi is a graph isomorphism, edges of A within H_{A} merge with the corresponding edges of B within H_{B} , so we do not end up with double edges. Clearly, H_{A} and H_{B} must indeed be isomorphic or else no gluing is possible. We will however focus on a different question: how many different graphs can we obtain by gluing the given A and B over the given isomorphic H_{A} and H_{B} ? This is answered by the following proposition, adapted from statement (2.7) in [ 9 ] to the graph-theoretic context. Instead, of gluing H_{A} directly with H_{B} , we can introduce an independent copy H of this graph and glue it onto H_{A} and H_{B} via all possible isomorphisms \psi_{A}:H\to H_{A} and \psi_{B}:H\to H_{B} . This point of view stresses symmetry between A and B while being equivalent to our original gluing construction. In what follows we fix arbitrary isomorphisms \gamma_{A}:H\to H_{A} and \gamma_{B}:H\to H_{B} . Let \operatorname{Aut}(A,H_{A}) be the group of all automorphisms of A leaving H_{A} invariant. Symmetrically, let \operatorname{Aut}(B,H_{B}) be the group of all automorphisms of B stabilising H_{B} . These automorphisms can be transferred into \operatorname{Aut}(H) by conjugating with \gamma_{A} and \gamma_{A} , respectively, giving us subgroups \operatorname{Aut}(A,H_{A})^{\gamma_{A}} and \operatorname{Aut}(B,H_{B})^{\gamma_{B}} of \operatorname{Aut}(H) . (Naturally, every element of \operatorname{Aut}(A,H_{A}) is first restricted to H_{A} and then conjugated by \gamma_{A} , and similarly, for the elements of \operatorname{Aut}(B,H_{B}) .) Proposition 5.6 . The number of non-isomorphic graphs formed by gluing A and B with respect to isomorphic subgraphs H_{A} and H_{B} coincides with the number of double cosets in the group \operatorname{Aut}(H) of its subgroups \operatorname{Aut}(A,H_{A})^{\gamma_{A}} and \operatorname{Aut}(B,H_{B})^{\gamma_{B}} . Note that here we only consider isomorphisms between resulting glued graphs that preserve A and B set-wise. In principle, there could be further isomorphisms, for example, the ones switching A and B or even more general ones. These are not accounted for in the above proposition. However, this will be irrelevant for our purposes. The final remark is that the complete set of different gluings \phi:H_{A}\to H_{B} is given by \{\gamma_{B}\alpha_{i}\gamma_{A}^{-1}\mid i=1,2,\ldots k\} , where k is the number of double cosets above and \alpha_{1},\alpha_{2},\ldots,\alpha_{k} are representatives of the double cosets. In our enumeration, the above proposition is applied to gluing the segments S_{x} and S_{y} over the respective handles. As we already mentioned, the handles must be of the same type: either both edges or both non-edges. Note that in either case \operatorname{Aut}(H) is of order 2 and the number of double cosets is one if the two vertices of the glued handle can be switched in the (handle-preserving) automorphism group of either of the two segments S_{x} and S_{y} . If the two vertices cannot be switched then the number of double cosets is two. Clearly, this gives us an easy way to enumerate all segment pairs (graphs obtained by gluing S_{x} and S_{y} ) up to isomorphism. In order to state the result of the enumeration, recall that we dropped all the segments of type (4,6) , and we are always gluing the first handles from both segments. Therefore, a segment pair can only be made of two segments of type (6,6) , or a segment of type (6,6) and a segment of type (6,4) , or two segments of type (6,4) , or two segments of type (4,4) . The following statement, established by enumeration, gives us the number of different segment pairs. Proposition 5.7 . There are 86333 different segment pairs in total. Among them, there are 281 segment pairs made of two segments of type (6,6) , 2249 segment pairs made of a segment of type (6,6) and a segment of type (6,4) , 4851 segment pairs made of two segments of type (6,4) , and 78952 segment pairs made of two segments of type (4,4) . From this statement, we see that the last type of segment pairs is by far the most numerous. However, this is offset by the fact that the number 24 of possible matchings between the cores of S_{x} and S_{y} arising in this case is much smaller than the number 720 of matchings required for the first three types. Hence the four types of segment pairs are in fact reasonably balanced in computational terms. We next discuss the algorithmic details of all these processes. 6 Steps 1 and 2: Building up T We keep all possible segments in a list according to the type of the segment. First, we have the 19 segments of type (6,6) , then the 78 segments of type (6,4) , and finally, the 303 segments of type (4,4) . Each segment S is stored with its vertices ordered in a particular way. First, we have the two handles, X and Y , then the vertices from S_{0}=S\setminus(X\cup Y) not contained in the cores C_{X} and C_{Y} , then the vertices in C_{Y}\setminus C_{X} , then C_{X}\setminus C_{Y} , and finally the vertices from C_{X}\cap C_{Y} . This is shown in the following table, where the numbers in the third column indicate the size of the part. Note that the last four numbers constitute the quad type of S . X 2 Y 2 none S\setminus(X\cup Y\cup C_{X}\cup C_{Y}) n_{S} right C_{Y}\setminus C_{X} r_{S} left C_{X}\setminus C_{Y} l_{S} both C_{X}\cap C_{Y} b_{S} Table 2: Vertices in a segment The first column indicates the meaning of the part: the two handles do not require explanation, the following part consists of vertices in neither of the two cores, hence the label ‘none’; the label ‘right’ indicates that those vertices belong only in the core for the second handle; ‘left’ means that these are in the core for the first handle; finally, ‘both’ indicates that these vertices are in both cores. (‘Left’/‘right’ was a useful mnemonic that we adopted during this project.) When we enumerate segment pairs, we always assume that S_{x} either precedes S_{y} on the list or S_{x} is the same segment as S_{y} . This guarantees that we do not overcount segment pairs. As we have already mentioned, we glue the first handle of S_{x} onto the first handle of S_{y} . Once we select a specific segment pair from our list of 86333 , we need to go at Step 1 through all possible matchings between the cores of S_{x} and S_{y} with respect to the handle Z=S_{x}\cap S_{y} , the first (‘left’) handle in both segments. These two cores are identified within the corresponding segment records as the union of the parts marked with ‘left’ and ‘both’, i.e., the cores are at the end of the record for both segments. Note that the two cores are of the same cardinality c\in\{4,6\} , as Z has the same type in S_{x} and S_{y} . Recall that our method involves checking the Gram matrix on an ever growing set of vertices. In other words, once we know all edges within the subset, i.e., the Gram matrix on this subset is fully known, we immediately want to check this Gram matrix for semi-positive definiteness. In principle, such a check becomes more and more expensive as the subset becomes bigger. However, as we build the set up by adding one vertex at a time, this amounts to adding one new row (and column) to the Gram matrix. Fortunately, the LDLT algorithm [ 5 ] , which we use to verify absence of negative eigenvalues, is iterative exactly in this sense, and so we can significantly save on time by doing just the iterative part corresponding to adding one row. The details of this realisation of the LDLT algorithm are in Appendix B . Having the cores at the end of the segment record means that the induced subgraph on the first 22-c vertices of the segment pair (the full size of a segment pair is 12+12-2=22 vertices) is the same regardless of the matching we add. That is, we need to account for the possible matchings only when dealing with the final c vertices. Recall that possible matchings between two cores C_{x}\subset S_{x} and C_{y}\subset S_{y} of equal size c are indexed by the elements of the symmetric group S_{c} . Since c\in\{4,6\} , we have 6!=720 matchings when Z is an edge and 4!=24 matchings when Z is a non-edge. Looking at Proposition 5.7 , we see that there are significantly more segment pairs where Z is a non-edge, so adding the matchings evens out those two cases. To add a matching to a given segment pair, we scan a pre-computed tree of depth c , which at each level i decides the neighbour in C_{x} of the i th vertex y_{i} from C_{y} . This allows us to add the data of y_{i} to the Gram matrix and check semi-positive definiteness. This results in a very efficient enumeration algorithm. Note that we had the option of using symmetry of the segment pair to cut down on the number of possible segment pairs with matching. However, in most cases the symmetry is trivial, and so we decided against using it, as it would not bring us much benefit and it would require a different enumeration tree for each symmetry type, significantly complicating the algorithm. As it turns out, none of the resulting segment pairs with matching (corresponding to the leaves of the enumeration tree) are eliminated by the semi-positive definiteness criterion. This is why we next add the third segment S_{z} at Step 2. Again, we could use the symmetries of the segment pair S_{x}\cup S_{y} and the segment S_{z} to reduce, using Proposition 5.6 , the number of ways of merging the first and second handles in S_{z} with second handles in S_{x} and S_{y} , respectively. However, we again decided against it, because we judged that it would not give us a significant decrease in runtime to justify the trade off, a less transparent algorithm. Hence we simply allowed all four ways of gluing the two handles of S_{z} onto the second handles of S_{x} and S_{y} . In hindsight, this may have been a questionable decision as the majority of the hardest cases came from symmetric configurations and so, in fact, it may have significantly increased the overall runtime by doing some slow configurations twice. Note that we again assume that S_{z} does not precede S_{y} (and hence also S_{x} ) in the list of segments, and this allows us to avoid the most obvious overcounting. Once the handles of S_{z} are identified with the corresponding handles of S_{x} and S_{y} , we still need to add two matchings, between the cores in S_{x} and S_{z} corresponding to the handle Y=S_{x}\cap S_{z} and between the cores in S_{y} and S_{z} corresponding to the handle X=S_{y}\cap S_{z} . Just like we used an enumeration tree to account for all matchings in the segment pair S_{x}\cup S_{y} , we utilise a similar idea and account for the two new matchings within a single precomputed tree of depth 8 (the cardinality of S_{z}\setminus(X\cup Y) ). Hence, at each level i , the tree chooses the additional neighbours of the i th vertex z_{i} of S_{z}\setminus(X\cup Y) in S_{x} and S_{y} . Referring to Table 2 , if z_{i} is in the ‘none’ part of the segment S_{z} then it has no additional neighbours and so we can immediately add this vertex to the Gram matrix and check semi-positive definiteness. If z_{i} is in the ‘right’ part of S_{z} then it has an additional neighbour in S_{y} . Symmetrically, if z_{i} is in the ‘left’ part then it has an additional neighbour in S_{x} . Finally, if z_{i} is in the ‘both’ part of S_{z} , it has two additional neighbours, one in S_{x} and the other in S_{y} . Again, once the neighbours of z_{i} are selected, we add the data of z_{i} to the Gram matrix and check semi-positive definiteness. From this discussion, it is clear that the exact structure and size of this second enumeration tree (we called it the big tree , as opposed to the smaller tree we use for adding the matching between the cores in S_{x} and S_{y} ) depends on the quad type (n_{S},r_{S},l_{S},b_{S}) of S=S_{z} . We precomputed the big trees for all quad types and then simply use the correct one depending on the quad type of S_{z} . Note that while the structure and the total size of the big tree varies from one quad type to another, the number of final configurations (leaves) in the big tree depends only on the types of the handles X and Y . Namely, we have exactly 6!6!=720^{2}=518400 leaves when both X and Y are edges, 6!4!=720\cdot 24=17280 leaves if Y is an edge and X is a non-edge, and 4!4!=24^{2}=576 leaves if both X and Y are non-edges. These numbers indicate the possible numbers of complete configurations T=S_{x}\cup S_{y}\cup S_{z} for each choice of a segment pair with a matching, S_{x}\cup S_{z} with the third segment S_{z} already glued in over the handles. This makes for really astronomical total numbers of possible configurations T , which would not be possible to enumerate and evaluate. What makes it a feasible project in the end is that we add vertices one by one and the semi-positive definiteness criterion kicks in a very non-trivial way after just a few (typically four or five) vertices of S_{z}\setminus(X\cup Y) are added. So we rarely, in fact, almost never, have to visit in our enumeration all leaves of the big tree. We do not have the exact data which proportion of all configurations is eliminated by expanding S_{x}\cup S_{y} to the full set T=S_{x}\cup S_{y}\cup S_{z} . By our observation, it is well in excess of 99\% . However, a tiny proportion of survivors ends up being a significant number of full configurations T which are semi-positive definite, and hence, in order to try and eliminate those, we need an extra step in the algorithm, adding vertices beyond T . 7 Step 3: Beyond T After extensive experiments trying to find a meaningful way to add additional vertices, we settled on the following scheme: we add vertices from G\setminus\hat{T} , where \hat{T}=Q\cup T , that are adjacent to the first vertex t from the handle X=S_{y}\cap S_{z} . This is the vertex number 13 in T . 7.1 Enumerating additional vertices Note that t has no neighbours in S_{x} and it has two neighbours in both S_{y} and S_{z} . Hence, within \hat{T} , the vertex t has 2+2+2=6 neighbours, if X is a non-edge, and t has 2+1+1+1=5 neighbours in \hat{T} , if X is an edge 1 1 1 For the reasons that will be explained later, we never encounter in the actual calculation the case where X is an edge. . In any case, t has at least 14-6=8 neighbours in G\setminus\hat{T} , and these are the vertices we aim to add to our configuration. Adding eight extra vertices to T brings the total to 38 vertices, which significantly exceeds the dimension 34 of E . Hence not only the Gram matrix on this larger set must be semi-positive definite, but also the rank of the Gram matrix cannot exceed 34 , which means that the radical must be of dimension at least 38-34=4 , and this is a super-strong condition. On the other hand, we do not know adjacency on the set of extra vertices, as we do not utilise any concept similar to segment here. We add the extra vertices one by one, using the restrictions that we now proceed to discuss. Lemma 7.1 . Suppose that u\in G\setminus\hat{T} , and u is adjacent to t . Then u has exactly two neighbours in S_{x} and it has exactly one additional (other than t ) neighbour in both S_{y} and S_{z} . This is immediate since u is not adjacent to any vertex in Q and \mu=2 . This means that u has the maximum of five and the minimum of three (if u is adjacent to vertices in both handles Y and Z ) neighbours in T . We pre-compute all such possible sets of neighbours in T . Lemma 7.2 . In total, there are exactly 2080 possible configurations of neighbours of u in T that satisfy Lemma 7.1 . Note that this set of possible sets of neighbours of extra vertices u only depends on how the segments are embedded in T , and so this calculation needs to be done only once, as its result, the array we call downs , is applicable to all T . However, a concrete T allows further elimination of some of these possibilities. First of all, we note that each u is uniquely identified by its neighbours in T . Lemma 7.3 . If u^{\prime}\in G\setminus\hat{T} has the same neighbours in T as u then u^{\prime}=u . Proof. Indeed, suppose that u^{\prime}\neq u . Since they have at least three common neighbours in T and \mu=2 , we must have that u and u^{\prime} are adjacent. Furthermore, since \lambda=3 , u and u^{\prime} have exactly three neighbours in T , one in each handle. Let t^{\prime} be their common neighbour in the handle Z=S_{x}\cap S_{y} . Then we know from Lemma 4.4 that t and t^{\prime} are non-adjacent and, at the same time, they have three common neighbours, y , u and u^{\prime} . This is a contradiction proving the claim. ∎ Hence, each element d of downs describes a unique potential neighbour u of t . 7.2 Eliminating impossible d To eliminate some d , we first compute the demand for all pairs of vertices from T . That is, given a pair t_{i},t_{j}\in T , with iList([1..30],j->0)); L:=List([1..40],i->List([1..30],j->0)); D:=[]; R:=List([1..30],i->List([1..30],j->0)); Id:=IdentityMat(30); AddOne:=function(r) local n,i,sum,j; n:=Length(r); for i in [1..n] do sum:=0; for j in [1..i-1] do sum:=sum+L[n][j]*L[i][j]*D[j]; od; if ii , we have 0=(e_{k},u_{i})=(e_{k},e_{i}-\sum_{j=1}^{i-1}L_{ij}u_{j})=(e_{k},e_{i})-\sum_{j=1}^{i-1}L_{ij}(e_{k},u_{j})=M_{ki}-\sum_{j=1}^{i-1}L_{ji}L_{kj}D_{jj} , since (e_{k},u_{j})=L_{kj}D_{jj} for all j\leq k . This yields M_{ki}=\sum_{j=1}^{i-1}L_{ji}L_{kj}D_{jj} , and the contradiction shows that the form is not semi-positive definite. It remains to notice that when this is first encountered we have n=k and M_{ki}=r_{i} . ∎ Hence indeed our function AddOne returns false exactly when the extended Gram matrix M is not semi-positive definite. We would like to retain the map \psi:\mathbb{R}^{n}\to\langle t_{1},t_{2},\ldots,t_{n}\rangle introduced in this proof to be used elsewhere in the paper. Typically, it will be with the full set T , that is, with n=30 . Then u\in\mathbb{R}^{30} can be viewed simply as the coefficient vector of \psi(u) with respect to the spanning set T=\{t_{1},t_{2},\ldots,t_{30}\} of W=\langle T\rangle . Since the dot product is positive definite on W , the vectors u_{i} with D_{ii}=(u_{i},u_{i})=0 are in the kernel of \psi and, in fact, such vectors u_{i} form a basis of \ker\psi . On the other hand, the vectors \psi(u_{i}) , where D_{ii}\neq 0 , form an orthogonal basis of W . The final comment in this section concerns the meaning of the matrix R=L^{-1} . Note that we have e_{i}=\sum_{j=1}^{i}L_{ij}u_{j}=\sum_{j=1}^{n}L_{ij}u_{j} , since L is lower triangular. This means that L is the transition matrix from the orthogonal basis \{u_{1},u_{2},\ldots,u_{n}\} to the standard basis \{e_{1},e_{2},\ldots,e_{n}\} of \mathbb{R}^{n} . Correspondingly, R=L^{-1} is the transition matrix from the standard basis to the orthogonal basis \{u_{1},u_{2},\ldots,u_{n}\} . In other words, the row R_{i} of R provides the coefficients of u_{i} with respect to the standard basis, or in simpler terms, R_{i}=u_{i} . Appendix C Projection matrix If the Gram matrix of the full set T happens to be semi-positive definite then we have to consider vertices beyond T and, at this stage, our strategy of checking semi-positive definiteness iteratively is not as effective, because we are not working with a pre-selected segment and, consequently, the graph structure on the additional set of vertices is not known. Hence we need another approach, and it involves computing the orthogonal projection of the additional vertices to the subspace W spanned by T . For a vertex u , we will have the list of its neighbours in T and hence we can form the vector r=(r_{1},r_{2},\ldots,r_{n}) , where n=|T|=30 and r_{i}=u\cdot t_{i} is the value of the dot product between u and the i th vertex t_{i}\in T . Hence r_{i}=\left\{\begin{array}[]{rl}\frac{2}{7},&\text{if }u\sim t_{i},\\ -\frac{1}{14},&\text{otherwise}\end{array}\right. We need to find a matrix P such that p=rP is the list of coefficients of the projection \operatorname{proj}_{W}(u) of u to W with respect to the spanning set T=\{t_{1},t_{2},\ldots,t_{n}\} . (That is, \operatorname{proj}_{W}(u)=\psi(p) , where \psi:\mathbb{R}^{n}\to W is the linear map introduced in Appendix B .) We need to make two comments. First, since T may in some cases be linearly dependent, the vector p is in general not unique. Secondly, for the same reason, some vectors r need to be eliminated because they lead to non semi-positive definiteness of the inner product on the expanded space \langle T\cup\{u\}\rangle . This happens when the entries in r yield non-orthogonality of u to some linear combinations of the vectors t_{i} that have zero length. Here is our function: # Vertex projection P:=List([1..30],i->List([1..30],j->0)); ComputeProjMat:=function() local i; P:=0*IdentityMat(30); for i in [1..30] do if D[i]<>0 then P:=P+TransposedMat([R[i]])*[R[i]]/D[i]; fi; od; end; Note that we again treat the output, the projection matrix P , as a global variable, because we want to have easy access to it from the main code. Here is the lemma that justifies our method of computing P . Recall that when we need P we have already determined the matrices L (strictly lower triangular) and D (diagonal), such that M=LDL^{T} is the Gram matrix of the set T . Furthermore, we also have R=L^{-1} . Let u_{i}=R_{i} be the i th row of the matrix R . Recall that u_{1},u_{2},\ldots,u_{n} is the orthogonal basis of \mathbb{R}^{n} with respect to the form (\cdot,\cdot) with the Gram matrix M . For generality, we allow an arbitrary n=|T| , but of course, in our application n=30 . Correspondingly, all matrices are n\times n . Let N=\left\{i\in\{1,2,\ldots,n\}\mid D_{ii}\neq 0\right\} . Lemma C.1 . For a vertex u\notin T identified by the vector r , with r_{i}=u\cdot t_{i} , i=1,2,\ldots,n , the projection of u onto W=\langle T\rangle=\langle t_{1},t_{2},\ldots,t_{n}\rangle coincides with w=\sum_{i=1}^{n}p_{i}t_{i} , where p=(p_{1},p_{2},\ldots,p_{n})=rP and P=\sum_{i\in N}\frac{1}{D_{ii}}R_{i}^{T}R_{i}. Proof. The projection vector w is identified by the property that w\cdot v=u\cdot v for all v\in W . In particular, w\cdot t_{i}=u\cdot t_{i}=r_{i} , for i=1,2,\ldots,n . Transferring this into \mathbb{R}^{n} , we are looking for a row vector p (coefficients of w with respect to the set T ) such that pM=r . If M is not positive definite, the set T is linearly dependent, and so such a vector p is not unique, but it is unique if we select it in the subspace \langle u_{i}\mid i\in N\rangle , which is a complement to the radical of the form (\cdot,\cdot) . We claim that the formulae in the lemma give us exactly such a vector. Indeed, suppose that p is a row vector such that pM=r and p is a linear combination of the vectors u_{i} , i\in N . Using that u_{i}=R_{i} , for all i , we get \displaystyle\displaystyle p \displaystyle=\sum_{i\in N}\frac{(p,u_{i})}{(u_{i},u_{i})}u_{i} \displaystyle=\sum_{i\in N}\frac{(p,R_{i})}{(R_{i},R_{i})}R_{i} \displaystyle=\sum_{i\in N}\frac{(p,R_{i})}{D_{ii}}R_{i} \displaystyle=\sum_{i\in N}\frac{1}{D_{ii}}(pMR_{i}^{T})R_{i} \displaystyle=pM\sum_{i\in N}\frac{1}{D_{ii}}R_{i}^{T}R_{i} \displaystyle=r\sum_{i\in N}\frac{1}{D_{ii}}R_{i}^{T}R_{i}. Note that, in line 4 of this calculation, the product pMR_{i}^{T} is a 1\times 1 matrix with the entry equal to (p,R_{i}) , and so we have a four-term matrix product here, which allows us to use associativity and distributivity in the following line. ∎ Thus, we have the correct formula for the projection matrix.