def toughness_aux(G):
    """Return for each k the number of components we can obtain at most
    be removing k vertices.  """
    n = len(G.vertices())
    res = [0 for i in range(n)]
    for s in Subsets(G):
        l = len(s)
        if l < n:
            H = G.copy(immutable=False)
            H.delete_vertices(s)
            res[l] = max(res[l], H.connected_components_number())
    return res

def toughness(G):
    """
    sage: [toughness(graphs.CompleteGraph(k)) for k in range(1,7)]
    [+Infinity, +Infinity, +Infinity, +Infinity, +Infinity, +Infinity]
    sage: [toughness(graphs.CycleGraph(k)) for k in range(4,9)]
    [1, 1, 1, 1, 1]
    sage: [toughness(graphs.PathGraph(k)) for k in range(3,9)]
    [1/2, 1/2, 1/2, 1/2, 1/2, 1/2]

    sage: [toughness(G) for G in graphs(5) if G.is_hamiltonian()]
    [1, 1, 1, 1, 1, 3/2, 3/2, +Infinity]
    """
    tl = toughness_aux(G)
    t = Infinity
    for k in range(2,max(tl)+1):
        # find minimal number of vertices to remove
        i = 0
        while tl[i] < k:
            i += 1
        t = min(t, i/k)
    return t

def statistic(G):
    return toughness(G)*lcm(range(1,G.num_verts()))