>     std::pair< graph_traits<Graph>::edge_descriptor, bool > p = add_edge
> (*vertices(g).first, *vertices(g).second, g);

The function vertices returns an iterator range. In my understanding an
iterator range is a pair of iterators [first, second) so that second
can be reached from first with increment operations, _but_ is not part
of the iterator range itself. It could be an iterator like one returned
by the end-function of a stl-vector. It shall not be dereferenced!