AddEdges

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

AddEdges[g,edgeList]

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.