As of Version 10, most of the functionality of the Combinatorica package is built into the Wolfram System. >>

gives graph g minus e. If g is undirected, then e is treated as an undirected edge; otherwise it is treated as a directed edge. If there are multiple edges between the specified vertices, only one edge is deleted.

will delete all edges between the specified pair of vertices. Using the tag Directed as a third argument in DeleteEdge is now obsolete.