What graph problems are hard to solve even for a small number of verticies?
I recommend you look at a list of NP-complete problems on graphs.  For each one, research whether there exists a known approximation algorithm.  For some problems we have hardness of approximation results (which say that there is no polynomial-time algorithm that achieves approximation factor $\alpha$, unless $P=NP$).  Those are potential candidates that might be of interest.  In particular, I'd recommend you study the standard methods for dealing with intractability, then look for a candidate problem where none of those seem to work.  You might also look at graph problems that are APX-complete as candidates worthy of further exploration.

For instance, graph coloring might be a possible candidate to look at.  I haven't studied that problems so I don't know whether good heuristics exist.  I doubt it will be hard on graphs with only 10-20 vertices, but it might be hard with somewhat larger graphs.