Finally I was able to locate (not explain) the "problem":
typedef adjacency_list <vecS , listS, directedS, VertexProperties, EdgeProperties> Graph;
listS for the VertexList is obviously not working... So I changed it to vecS - but an explanation would be nice...
Because even the tutorial says it is okay to use listS or am I wrong?
http://www.boost.org/doc/libs/1_35_0/libs/graph/doc/using_adjacency_list.html#sec:choosing-graph-type

Using listS can be a bit tricky... it means that you either have to add a vertex_index_t property to all of the vertices in your graph, which provides a mapping from vertices to a index in the range [0, num_vertices(g)), or you have to create a separate property map that does the same thing.

- Doug