Conway's 99 Graph Conjecture asks if there exists a graph with \(99\) vertices such that, for each pair of vertices, either the pair is adjacent and contained in a unique triangle, or the pair is not adjacent and contained in a unique square. It is known that there exists a graph with \(9\) vertices and another graph with \(243\) vertices that have this property. Furthermore, unless the number of vertices is \(9\), \(99\), \(243\), \(6273\), or \(494019\) it is impossible for such a graph to exist. Thus, Conway's Conjecture asks for the smallest unknown number.
Caitlin Hutnyk, in her REU, proposed a genetic algorithm approach to finding such a graph. She introduced a score function that, informally speaking, counts the number of defects in the graph. Importantly, a score of \(0\) implies that such a graph has been found. The scoreboard keeps tracks of the lowest scoring graphs in an attempt to find a solution to Conway's 99 Conjecture.
More formally, consider a pair of vertices \(u, v \in V(G)\). We have two cases. If \(u, v\) are adjacent, they should have one common neighbor to be contained in a unique triangle and if \(u, v\) are not adjacent, they have two neighbors in common to be contained in a unique square. If the pair \(u, v\) satisfies either condition they should contribute a score of \(0\).
For a pair \(u, v\) one can count the number of common neighbors using the adjacency matrix of \(G\), call it \(A\). In particular, \(A^{2}_{uv}\) gives the number of common neighbors between \(u\) and \(v\). Hence, we may score a pair as follows \[\mathsf{Score}(u, v) = \begin{cases} |A^{2}_{uv} - 1| & uv \in E(G) \\ |A^{2}_{uv} - 2| & uv \notin E(G) \end{cases}\]
Thus, the Hutnyk score of \(G\) is the \(\sum_{u,v\in V(G)}\mathsf{Score}(u,v)\). As mentioned in Hutnyk's REU, this may be rewritten as: \[\text{tr}((A^{2} - 2J + A)^2) - 12^{2}\times 99\] where \(J\) is the matrix such that every entry is \(1\).
Please submit your graph as a JSON file. The JSON file should correspond to an adjacency list of the graph \(G\). The vertices should be labelled \(0\) through \(98\). The server will then parse the submission and score the graph based on the Hutnyk score.