def max_cardinality_heuristic(G):
    """Computes an upper bound on the treewidth of graph G based on
    the max-cardinality heuristic for the elimination ordering.

    Parameters
    ----------
    G : NetworkX graph
        The graph on which to compute an upper bound for the treewidth.

    inplace : bool
        If True, G will be made an empty graph in the process of
        running the function, otherwise the function uses a copy
        of G.

    Returns
    -------
    treewidth_upper_bound : int
        An upper bound on the treewidth of the graph G.

    order : list
        An elimination order that induces the treewidth.

    Examples
    --------
    This example computes an upper bound for the treewidth of the :math:`K_4`
    complete graph.

    >>> import dwave_networkx as dnx
    >>> import networkx as nx
    >>> K_4 = nx.complete_graph(4)
    >>> dnx.max_cardinality_heuristic(K_4)
    (3, [3, 1, 0, 2])

    References
    ----------
    Based on the algorithm presented in [GD]_

    """
    # we need only deal with the adjacency structure of G. We will also
    # be manipulating it directly so let's go ahead and make a new one
    adj = {v: set(G[v]) for v in G}

    num_nodes = len(adj)

    # preallocate the return values
    order = [0] * num_nodes
    upper_bound = 0

    # we will need to track the nodes and how many labelled neighbors
    # each node has
    labelled_neighbors = {v: 0 for v in adj}

    # working backwards
    for i in range(num_nodes):
        # pick the node with the most labelled neighbors
        v = max(labelled_neighbors, key=lambda u: labelled_neighbors[u] + random())
        del labelled_neighbors[v]

        # increment all of its neighbors
        for u in adj[v]:
            if u in labelled_neighbors:
                labelled_neighbors[u] += 1

        order[-(i + 1)] = v

    for v in order:
        # if the number of neighbours of v is higher than upper_bound, update
        dv = len(adj[v])
        if dv > upper_bound:
            upper_bound = dv

        # make v simplicial by making its neighborhood a clique then remove the node
        # add v to order
        _elim_adj(adj, v)

    return upper_bound, order
Computes an upper bound on the treewidth of graph G based on
    the max-cardinality heuristic for the elimination ordering.

    Parameters
    ----------
    G : NetworkX graph
        The graph on which to compute an upper bound for the treewidth.

    inplace : bool
        If True, G will be made an empty graph in the process of
        running the function, otherwise the function uses a copy
        of G.

    Returns
    -------
    treewidth_upper_bound : int
        An upper bound on the treewidth of the graph G.

    order : list
        An elimination order that induces the treewidth.

    Examples
    --------
    This example computes an upper bound for the treewidth of the :math:`K_4`
    complete graph.

    >>> import dwave_networkx as dnx
    >>> import networkx as nx
    >>> K_4 = nx.complete_graph(4)
    >>> dnx.max_cardinality_heuristic(K_4)
    (3, [3, 1, 0, 2])

    References
    ----------
    Based on the algorithm presented in [GD]_