Hullo boost gurus, The code at detail/adjacency_list.hpp:1815 is currently like this... remove_vertex_dispatch(Graph& g, vertex_descriptor u, boost::bidirectional_tag) { //.... g.m_vertices.erase(g.m_vertices.begin() + u); //... for (v = 0; v < V; ++v) reindex_edge_list(g.out_edge_list(v), u, edge_parallel_category()); //... If I am understanding this correctly, after erasing a vertex we go through all vertices in the graph and reindex their edges/ This is because there may be edges to/from vertices after u. But this can be avoided if u was the last vertex in the graph, right? So this... //.... g.m_vertices.erase(g.m_vertices.begin() + u); //.... if (u != num_vertices(g)) { //all the re-indexing code } is a valid optimization isn't it? My graph grows and shrinks a lot (but always at highest vertex number) and this code change had a dramatic effect on runtime. -- Vikram Shrowty <vikram@lsil.com>