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

gives graph g minus the list of edges edgeList. If g is undirected, then the edges in edgeList are treated as undirected edges; otherwise they are treated as directed edges. If there are multiple edges that qualify, then only one edge is deleted.

will delete all edges that qualify. If only one edge is to be deleted, then edgeList can have the form {s,t}; otherwise it has the form {{s1,t1},{s2,t2},}.