  A Neumaier graph is a non-complete edge-regular graph containing a regular
clique. In this work, we prove several results on the existence of small
strictly Neumaier graphs. In particular, we present a theoretical proof of the
uniqueness of the smallest strictly Neumaier graph with parameters
$(16,9,4;2,4)$, we establish the existence of a strictly Neumaier graph with
parameters $(25,12,5;2,5)$, and we disprove the existence of strictly Neumaier
graphs with parameters $(25,16,9;3,5)$, $(28,18,11;4,7)$, $(33,24,17;6,9)$,
$(35,22,12;3,5)$ and $(55,34,18;3,5)$. Our proofs use combinatorial techniques
and a novel application of integer programming methods.
