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][1] 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][2] 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.


  [1]: http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&ved=0CCsQFjAA&url=http://www.math.ucsd.edu/~ronspubs/78_12_matrix_polynomials.pdf&ei=tb1KUuvPNubm4QT3loDgDw&usg=AFQjCNForRfme5huW7H47YBzw8OouvanHg&sig2=wf5VhX6SUvVgicgeDRJ_pg&bvm=bv.53371865,d.bGE
  [2]: http://arxiv.org/abs/1303.4517