Dear members, using the graph concepts for a case where I frequently add or remove edges I came across an inconsistency: removing an edge may invalidate the edge counter because it does not check whether the edge existed or not. This is the code from the header file boost/graph/adjacency_matrix.hpp: template <typename D, typename VP, typename EP, typename GP, typename A> void remove_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, adjacency_matrix<D,VP,EP,GP,A>& g) { --(g.m_num_edges); detail::set_edge_exists(g.get_edge(u,v), false, 0); } Whereas in the case of adding an edge the check is done: template <typename D, typename VP, typename EP, typename GP, typename A> std::pair<typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor, bool> add_edge(typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor u, typename adjacency_matrix<D,VP,EP,GP,A>::vertex_descriptor v, const EP& ep, adjacency_matrix<D,VP,EP,GP,A>& g) { typedef typename adjacency_matrix<D,VP,EP,GP,A>::edge_descriptor edge_descriptor; if (detail::get_edge_exists(g.get_edge(u,v), 0) == false) { ++(g.m_num_edges); detail::set_property(g.get_edge(u,v), ep, 0); detail::set_edge_exists(g.get_edge(u,v), true, 0); return std::make_pair (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))), true); } else return std::make_pair (edge_descriptor(true, u, v, &detail::get_property(g.get_edge(u,v))), false); } I would suggest a similar check for "remove_edge" instead of blindly counting down. Regards, Moritz