import itertools


def _elim_adj(adj, n):
    """eliminates a variable, acting on the adj matrix of G,
    returning set of edges that were added.

    Parameters
    ----------
    adj: dict
        A dict of the form {v: neighbors, ...} where v are
        vertices in a graph and neighbors is a set.

    Returns
    ----------
    new_edges: set of edges that were added by eliminating v.

    """
    neighbors = adj[n]
    new_edges = set()
    for u, v in itertools.combinations(neighbors, 2):
        if v not in adj[u]:
            adj[u].add(v)
            adj[v].add(u)
            new_edges.add((u, v))
            new_edges.add((v, u))
    for v in neighbors:
        adj[v].discard(n)
    del adj[n]
    return new_edges