def _maximal_matching_qubo(G, edge_mapping, magnitude=1.):
    """Generates a QUBO that when combined with one as generated by _matching_qubo,
    induces a maximal matching on the given graph G.
    The variables in the QUBO are the edges, as given my edge_mapping.

    ground_energy = -1 * magnitude * |edges|
    infeasible_gap >= magnitude
    """
    Q = {}

    # for each node n in G, define a variable y_n to be 1 when n has a colored edge
    # and 0 otherwise.
    # for each edge (u, v) in the graph we want to enforce y_u OR y_v. This is because
    # if both y_u == 0 and y_v == 0, then we could add (u, v) to the matching.
    for (u, v) in G.edges:
        # 1 - y_v - y_u + y_v*y_u

        # for each edge connected to u
        for edge in G.edges(u):
            x = edge_mapping[edge]
            if (x, x) not in Q:
                Q[(x, x)] = -1 * magnitude
            else:
                Q[(x, x)] -= magnitude

        # for each edge connected to v
        for edge in G.edges(v):
            x = edge_mapping[edge]
            if (x, x) not in Q:
                Q[(x, x)] = -1 * magnitude
            else:
                Q[(x, x)] -= magnitude

        for e0 in G.edges(v):
            x0 = edge_mapping[e0]
            for e1 in G.edges(u):
                x1 = edge_mapping[e1]

                if x0 < x1:
                    if (x0, x1) not in Q:
                        Q[(x0, x1)] = magnitude
                    else:
                        Q[(x0, x1)] += magnitude
                else:
                    if (x1, x0) not in Q:
                        Q[(x1, x0)] = magnitude
                    else:
                        Q[(x1, x0)] += magnitude

    return Q
Generates a QUBO that when combined with one as generated by _matching_qubo,
    induces a maximal matching on the given graph G.
    The variables in the QUBO are the edges, as given my edge_mapping.

    ground_energy = -1 * magnitude * |edges|
    infeasible_gap >= magnitude