I too got surprised in understanding the nature of vertex/edge descriptors when getting familiar to boost.graph. The vertex descriptors are simply indexes for vecS. This means that they will change as vertices are deleted. They can't be used as a unique key of a specific vertex. The edge descriptors are by necessity, more complex. They are simple objects that contain attributes for their target/source vertices, plus a pointer to a property object. This object does not have an operator< method. This has lead me to using internal properties when using mutable graphs and only using descriptors external to a graph in a temporary way so I don't have to deal the graph changing. Greg Emerson wrote:

Sorry, I forgot to mention that I have set VertexList=vecS (and wish to keep it that way).

Thanks again, Greg Emerson