http://www.boost.org/libs/graph/doc/Graph.html mentions it: Valid Expressions boost::graph_traits<G>::null_vertex() Returns a special boost::graph_traits<G>::vertex_descriptor object which does not refer to any vertex of graph object which type is G. http://www.boost.org/libs/graph/doc/graph_concepts.html does not ...