N_vertices = 7 # 8 takes a long time (perhaps an hour)

def is_complete_tripartite(G):
    """
    Return n1 <= n2 <= n3 or False.
    """
    deg = G.degree()
    degs = set(deg)
    if len(degs) > 3:
        return False
    elif len(degs) == 3:
        n1, n2, n3 = [deg.count(d) for d in degs]
        if G.is_isomorphic(graphs.CompleteMultipartiteGraph([n1, n2, n3])):
            return tuple(sorted((n1, n2, n3)))

    elif len(degs) == 2:
        N1, N2 = [deg.count(d) for d in sorted(degs)]
        n1 = N1
        n2 = n3 = N2 // 2
        if G.is_isomorphic(graphs.CompleteMultipartiteGraph([n1, n2, n3])):
            return tuple(sorted((n1, n2, n3)))
        n1 = N2
        n2 = n3 = N1 // 2
        if G.is_isomorphic(graphs.CompleteMultipartiteGraph([n1, n2, n3])):
            return tuple(sorted((n1, n2, n3)))

    elif len(degs) == 1:
        n1 = n2 = n3 = G.num_verts() // 3
        if G.is_isomorphic(graphs.CompleteMultipartiteGraph([n1, n2, n3])):
            return tuple(sorted((n1, n2, n3)))

    return False


def competition_graph(D):
    """
    Return the competition graph of a DAG.
    """
    n = D.num_verts()
    G = Graph(n)
    for i in range(1,n):
        for j in range(i):
            if set(D.neighbors_out(i)).intersection(D.neighbors_out(j)):
                G.add_edge(i,j)
    return G.canonical_label().copy(immutable=True)

@cached_function
def competition_graphs(n):
    """
    sage: [len(competition_graphs(n)) for n in range(8)]
    [1, 1, 1, 2, 4, 10, 29, 116]
    """
    return set(competition_graph(D) for D in digraphs(n, property = lambda g: g.is_directed_acyclic()))

def competition_number_naive(G, N):
    """
    sage: [(G, competition_number_brute(G, N_vertices-G.num_verts())) for n in range(1, 6) for G in graphs(n)]
    """
    n = G.num_verts()
    H = G.copy()
    if H.canonical_label().copy(immutable=True) in competition_graphs(H.num_verts()):
        return 0
    for i in range(1, N):
        H.add_vertex()
        if H.canonical_label().copy(immutable=True) in competition_graphs(H.num_verts()):
            return i

def statistic(G):
    """special cases due to

    * [1] Suh-Ryung Kim, Fred S. Roberts, "Competition numbers of graphs with a small number of triangles", DISCRETE APPLIED MATHEMATICS 153-162

    * [2] Suh-Ryung Kim, Yoshio Sano, Discrete Applied Mathematics, Volume 156, Issue 18, 28 November 2008, The competition numbers of complete tripartite graphs

    * [3] Li, Bo-Jr, and Gerard J. Chang. "Competition numbers of complete r-partite graphs." Discrete Applied Mathematics 160.15 (2012): 2271-2276.

    """
    k = competition_number_naive(G, N_vertices-G.num_verts())
    if k is not None:
        return k
    
    if G.is_chordal() and min(G.degree()) > 0:
        # [2]
        return 1
    if not G.is_connected():
        return
    n = G.num_verts()
    # [3], Theorem 5
    N = is_complete_tripartite(G)
    if N:
        n1, n2, n3 = N
        if n2 >= n3 + 2:
            return n1*n2 - n + 2
        elif n2 == n3 + 1 or n2 == n3 == 1:
            return n1*n2 - n + 3
        elif n2 == n3 >= 2:
            return n1*n2 - n + 4
    t = G.triangles_count()
    if t == 0:
        # [1]
        return G.num_edges() - G.num_verts() + 2
    if t == 1:
        # [1]
        if G.is_even_hole_free() and G.is_odd_hole_free():
            return G.num_edges() - G.num_verts() + 1
    return