After the initial graph implementation i started looking more at the the specializations and cabilities that were added to graphs to make them appropriate for certain situations. Two of those that came up were the directed and undirected graphs.

So far these are what I've come up with:

       public interface IUndirectedGraph<A> : IGraph<A> {                                                               
                ///A complete graph is an undirected graph in which every                                  
                ///pair of vertices is adjacent.                                                                         
                bool Complete { get; }                                                                                   
                                                                                                                         
                ///A bipartite graph is an undirected graph G = (V, E) in                                  
                ///which V can be partitioned into two sets V1 and                                            
                ///V2 such that (u, v) ∈ E implies that either                                           
                ///(u ∈ V1 and v ∈ V2) or                                                
                ///(u ∈ V2 and v ∈ V1).  That is, all edges                              
                ///go between the two sets V1 and V2.                                              
                bool Bipartite { get; }                                                                                  
                                                                                                                         
                ///An undirected graph is connected if every pair of vertices                              
                ///is connected by a path.                                                                               
                bool Connected { get; }                                                                                  
        } 

The directed graph allows for further operations:

        public interface IDirectedGraph<A> : IGraph<A> {
               ///Given a directed graph G = (V, E), the undirected graph of                              
                ///G is the undirected graph G' = (V, E'), where (u, v) ∈ E' if and                                 
                ///only if u ≠ v and (u, v) ∈ E.  That is, the undirected version                                
                ///contains the edges of G "with their directions removed" and with                                      
                ///self-loops eliminated.  (Since (u, v) and (v, u) are the same edge in an                              
                ///undirected graph, the undirected version of a directed graph contains it                              
                ///only once, even if the directed graph contains both edges (u, v) and                                  
                ///(v, u).)                                                                                              
                IUndirectedGraph<A> ToUndirectedGraph();                                                                  
                                                                                                                         
                ///A directed class is strongly connected if every two                                     
                ///vertices are reachable from each other.                                                               
                bool StronglyConnected { get; }                                                                          
                                                                                                                         
                ///Given a directed graph D=(V, E), a subgraph S=(V', E') is a strongly connected component if           
                ///a) S is strongly connected, and,
                ///b) for all vertices u such that u ∈ V and u ∉ V' for which (u,v) ∈ E
                ///This returns the set of all strongly connected components in this directed graph                      
                ISet<ISet<A>> StronglyConnectedComponents { get; }                                                       
                                                                                                                         
                ///In a directed graph, the out-degree of a vertex is the                                  
                ///number of edges leaving it                                                                            
                int OutDegree(A vertex);                                                                                 
                                                                                                                         
                ///In a directed graph, the in-degree of a vertex is the                                   
                ///number of edges entering it.                                                                      
                int InDegree(A vertex);                                                                                  
                                                                                                                         
                ///Returns all the vertices that have an edge pointing to this vertex                                    
                ISet<A> InConnections(A vertex);                                                                         
                                                                                                                         
                ///Returns all the vertices that this vertex has an edge to                                              
                ISet<A> OutConnections(A vertex);                                                                        
                                                                                                                         
                ///Returns G transpose, which is defined to be the graph G' = (V,E tranpose),                            
                ///where E transpose  = {(u,v) : (v,u) \in E}                                                            
                DirectedGraph<A> Transpose { get; }                                                                      
                                                                                                                         
                                                                                                                         
                ISet<IList<A>> SimpleCycles { get; }   
        }