Actually, I wasn't defining my own graph type. I've been using the CSR template class which was definitely an improvement over the adjacency list in terms of memory usage. I definitely have no use for adding and removing vertices on the fly. However, I am willing to look into defining my own graph. Do you think it's not beyond someone who is only a mediocre C++ programmer? I've been reading the doc site, but I haven't found any information about how to create my own graph. Could you please tell me where to look?

I think your best bet may be to modify the CSR graph types to use something other than size_t. Copy it, rename the type, and change it to suit your needs. That's close enough to creating your own graph type :)

I'm not entirely convinced that the benefits will outweigh the cost here. Maybe you'll save a couple MB, but you might do so at the expense of performance.