I think this function falls into the same category as edge(), which I'm starting to believe is exactly like iterator operations
distance(), advance(), next() and prev(). Not part of a concept, not a full-fledged algorithm, but nonetheless an operation that
can be implemented for every graph, with varying degrees of efficiency.

I agree. Should vertex() by default just be vertex(i, g) = {vertex_iterator it = vertices(g).first; advance(it, i); return *it;}? I don't think we can guarantee that matches the vertex_index map, though.

Does that mean that mean that we minimally require VertexListGraph<G> (in what I will not refer to as C?? syntax).

I know of only one adaptor that doesn't model VertexListGraph (edge_list), but that's just a weird data structure anyway. Actually Michael Lopez (SoC09, function graphs) has cases where a function does not model this concept, but that's a weird data structure too.

Maybe vertex is more like swap(), where we have a general algorithm with lots of specializations?

For edge(), I imagine we should have a trait for whether the out edges of a vertex are sorted, and then we can use logarithmic or linear-time algorithms. Particular graphs can specialize it for their own types (such as for adjacency_matrix's constant-time version). The edge_range() function should be the same thing, except that it requires that the edges are sorted in some way so that parallel edges are together (or we can use a filtered_iterator which would be a lot slower).

Logically that sounds about right. The following is purely hypothetical.

template <EdgeListGraph G>
pair<Edge, bool>edge(Vertex u, Vertex v, G const& g)
{ for(...) { if source(e, g) == u && target(e, g) == v) return {e, true}; } }

template <AdajcencyMatrix G>
pair<Edge, bool> edge(Vertex u, Vertex v, G const& g)
{ return g(u, v); }

template <IncidenceGraph G>
requires Range<G::out_edge_range>
pair<Edge, bool> edge(Vertex u, Vertex v, G const& g)
{ /* linear search in out_edges */ }

template <IncidenceGraph G>
requires SortedRange<G::out_edge_range>
pair<Edge, bool> edge(Vertex u, Vertex v, G const& g)
{ /* binary search in out_edges */ }

template <IncidenceGraph G>
requires AssociativeContainer<G::out_edge_range>
pair<Edge, bool> edge(Vertex u, Vertex v, G const& g)
{ /* use x.find() */ }

We can map these back to tag dispatch with a little bit of work.

The biggest problem I see here is that the BGL doesn't let us easily reason about the internal properties of out edge lists for adjacency list-like data structures or adaptors. It would be one thing to return the a legitimate range or reference to a container, but that's not where we are right now.

One might require member functions for efficient edge queries like my theoretical adjacency_matrix () overload. That would certainly reduce the requirements on overloads, but leaves us more or less where we are now (maybe?)

I wonder if this also admits the existence of an AdjacencyList concept.