I looked at runtime statements here: https://www.boost.org/doc/libs/1_85_0/libs/graph/doc/using_adjacency_list.ht... Fore remove_edge() there is no O(1) option listed. On the other hand in Boost graph code I see this O(1) remove_edge() in boost/graph/detail/adjacency_list.hpp: template < class Config > struct directed_edges_helper { ... // O(1) inline void remove_edge(typename Config::out_edge_iterator iter) { std::cerr << "foobar" << std::endl; typedef typename Config::graph_type graph_type; graph_type& g = static_cast< graph_type& >(*this); typename Config::edge_descriptor e = *iter; typename Config::OutEdgeList& el = g.out_edge_list(source(e, g)); el.erase(iter.base()); } }; So my questions is for which graph and how I can make use of that O(1) function to remove an edge. It seems to be for directed graph only. While I need it for undirected graph, being able to use that O(1) function for directed graph would be a first step. Regards, Hermann Stamm-Wilbrandt.