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

gives graph g with the new edges in edgeList added. edgeList can have the form {a,b} to add a single edge {a,b} or the form {{a,b},{c,d},}, to add edges {a,b},{c,d}, or the form {{{a,b},x},{{c,d},y},}, where x and y can specify graphics information associated with {a,b} and {c,d}, respectively.