I'm using a boost.graph via: typedef boost::adjacency_listboost::vecS,boost::vecS,boost::bidirectionalS GraphT; In my application, I've decided to use external maps. I have discovered a problem using vertex descriptors as a key of a map. Basically, in doing a remove_vertex sequence involving vertex descriptors 5, 3, 2, I discovered that the next vertex descriptor produced by add_vertex was 4. At this point the insert into my map failed because this element already existed. Given the mutable nature of vertex descriptors, I don't see how they can be used as a key in a map. I'm contemplating two options at this point. 1. Switch from map to vector in storing my vertex property externally. 2. Switch to internal properties. My questions are: 1. Is the first option viable? As I see things, vertex descriptors are always contiguous and in the range (0..num_vertices(graph)]. Is this true? 2. Do internal "maps" avoid this type of problem?