def pattern_positions_number(E, n, pattern_n, pattern_E, pattern_N,
                             upper_bound=None):
    """
    Return the number of subsets of vertices realising the given pattern.

    INPUT:

    - E, the edges of a graph with vertices 0,...,n-1
    - n, the number of vertices of a graph
    - pattern_n, the size of the pattern graph
    - pattern_E, a list of pairs of vertices which must occur
    - pattern_N, a list of pairs of vertices which must not occur

    """
    res = 0
    for V in Subsets(range(n), pattern_n)._fast_iterator():
        HV = sorted(V)
        if (all((HV[u], HV[v]) in E for u, v in pattern_E) and
            not any((HV[u], HV[v]) in E for u, v in pattern_N)):
            res += 1
            if upper_bound is not None and res >= upper_bound:
                return res
    return res

def occurrences(G, pattern_n, pattern_E, pattern_N):
    """
    The minimal number of occurrences of the given pattern in the set of all orderings of the vertices.

    paths
    sage: [(G, occurrences3(G, 3, [(0,2)], [])) for G in graphs(5)]

    stars
    sage: view([G for G in graphs(4) if avoids(G, 3, [(0,1)], [])])

    """
    n = G.num_verts()
    o = None
    tested = set()
    EG = G.edges(labels=False)
    for pi in Permutations(n):
        EH = [(pi[u]-1, pi[v]-1) for u, v in EG]
        EH = frozenset([(u, v) if u < v else (v, u) for u,v in EH])
        if EH in tested:
            continue
        tested.add(EH)
        if o is None:
            o = pattern_positions_number(EH, n, pattern_n, pattern_E, pattern_N)
        else:
            o = min(o, pattern_positions_number(EH, n, pattern_n, pattern_E, pattern_N, o))
    return o

def statistic(G):
    return occurrences(G, 3, [(0,1)], [])