Let $G$ be a simple connected graph $D(G)$ its distance matrix and $n_{+}(G), n_{-}(G)$ the number of positive and negative eigenvalues of $D(G)$ respectively.

We call a graph $G$ optimistic if $n_{+}(G) > n_{-}(G).$ The notion being motivated by a remark of Graham and Lovász saying that is not known if such graphs exists.

A computer search indicates that there is no optimistic graph on up to 11 vertices. Yet it can be easily seen that the Paley graphs of order $n > 13$ have this property. More generally every conference graph does and there are many other examples of optimistic graphs as well.

The question that remains is

Is there any optimistic graph of order $12$? If not is the Paley graph of order $13$ the unique smallest optimistic graph?

My computational resources are just slightly too low to tackle this by a computer program while my intellect is way out to be able to reduce the search space or construct an example by hand.

Hence I leave it here in case anyone can run a computer program or suggest some reductions on the search space.

Edit. The distance matrix $D = (d_{i,j})$ of a connected graph with vertex set $_1,\ldots,v_n$ is the matrix whose entries are $d_{i,j} = d(v_i,v_j)$