def statistic(G):
    mu = lower_and_upper_bounds(G.copy(immutable=True))
    if mu[0] == mu[1]:
        return mu[0]

@cached_function
def lower_and_upper_bounds(G, assume_Colin_conjecture=False):
    if G.is_clique():
        return (G.num_verts()-1, G.num_verts()-1)
    
    if G.num_verts() >= 2 and G.num_edges() == 0:
        # Goldberg, Berman (2011), prop. 6.7
        return (1,1)

    w = G.clique_number()
    # Goldberg, Berman (2011), cor. 2.4
    lower = w-1
    # Goldberg, Berman (2011), thm. 2.3 and mu(K_n)=n-1
    upper = G.num_verts()-1

    degrees = G.degree()
    if max(degrees) == 2 and G.is_forest():
        # Goldberg, Berman (2011), thm 2.6 (1)
        upper = 1
    elif G.is_circular_planar():
        # Goldberg, Berman (2011), thm 2.6 (2)
        upper = 2
    elif G.is_planar():
        # Goldberg, Berman (2011), thm 2.6 (3)
        upper = 3

    # Goldberg, Berman (2011), thm 5.4
    upper = min(upper, G.treewidth()+1)

    if G.is_chordal():
        # Goldberg, Berman (2011), thm 4.1
        upper = min(upper, w)

    if assume_Colin_conjecture:
        # Goldberg, Berman (2011), conj 2.7
        lower = max(lower, G.chromatic_number()-1)

    # Holst, Lovasz, and Schrijver (1999)
    # see Tait (2017), thm 7
    for v, d in G.degree(labels=True).iteritems():
        H = G.copy(immutable=False)
        H.delete_vertex(v)
        H = H.copy(immutable=True)
        mu_H = lower_and_upper_bounds(H, assume_Colin_conjecture=assume_Colin_conjecture)
        # equality is achieved if G has at least one edge (which we know at this point) and
        # v is connected to all other vertices
        if mu_H[0] == mu_H[1] and d == G.num_verts()-1:
            return (mu_H[0]+1, mu_H[0]+1)
                    
        upper = min(upper, mu_H[1] + 1)
        if lower == upper:
            return (lower, upper)

    return (lower, upper)