def minor_min_width(G):
    """Computes a lower bound for the treewidth of graph G.

    Parameters
    ----------
    G : NetworkX graph
        The graph on which to compute a lower bound on the treewidth.

    Returns
    -------
    lb : int
        A lower bound on the treewidth.

    Examples
    --------
    This example computes a lower bound for the treewidth of the :math:`K_7`
    complete graph.

    >>> K_7 = nx.complete_graph(7)
    >>> dnx.minor_min_width(K_7)
    6

    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(u for u in G[v] if u != v) for v in G}

    lb = 0  # lower bound on treewidth
    while len(adj) > 1:

        # get the node with the smallest degree
        v = min(adj, key=lambda v: len(adj[v]))

        # find the vertex u such that the degree of u is minimal in the neighborhood of v
        neighbors = adj[v]

        if not neighbors:
            # if v is a singleton, then we can just delete it
            del adj[v]
            continue

        def neighborhood_degree(u):
            Gu = adj[u]
            return sum(w in Gu for w in neighbors)

        u = min(neighbors, key=neighborhood_degree)

        # update the lower bound
        new_lb = len(adj[v])
        if new_lb > lb:
            lb = new_lb

        # contract the edge between u, v
        adj[v] = adj[v].union(n for n in adj[u] if n != v)
        for n in adj[v]:
            adj[n].add(v)
        for n in adj[u]:
            adj[n].discard(u)
        del adj[u]

    return lb