A second design approach uses composition as a member rather than private inheritance - not for any particular reason, I'm just more familiar with composition. Now, the prototype looks like this:

namespace boost {
  template <class VL, class EL, class OEL, class VP, class EP, class GP>
  class undirected_graph
  {
    typedef adjacency_list<OEL, VL, undirectedS, VP, EP, GP, EL> graph_type;
    graph_type g;

  public:
    inline graph_type& impl()
    { return g; }
  
    inline const graph_type& impl() const
    { return g; }

    // other stuff so we comply with graph_traits<>
  };

  // example add_vertex() function...
  template <class VL, class EL, class OEL, class VP, class EP, class GP>
  inline undirected_graph<VL, EL, OEL, VP, EP, GP>::vertex_descriptor
  add_vertex(undirected_graph<VL, EL, OEL, VP, EP, GP> &g)
  {
    return add_vertex(g.impl());  // calls add_vertex() for adjacency_list
  }
}

Rationale

This is essentially a direct migration of my first design using inheritance to composition. Funtionally, it should be identical to the first, except that it should completely eliminate strange name lookup artifacts caused by inheritance (especially if I write this class in a new boost::graph namespace.

Remarks

Clearly a very different approach, but once complete it should preserve all of the concept requirements given in the documentation. Interestingly, this is somewhat similar to graph adapter classes except that we aren't really adapting the adjacency list to a different purpose - we're just reducing the "abstractness" of the class by requiring (in this case), that it is instantiated with the undirectedS parameter. This approach is also a little more flexible than the previous in that we can add to this class without fear of unexpected consequences in the details of the original implementation. Of course, with this I'll have to write more code.