def statistic(G):
    """Return the smallest number such that Alice has a winning strategy.

    EXAMPLES:

        sage: [statistic(graphs.PathGraph(r)) for r in range(2,8)]
        [1, 2, 2, 3, 3, 3]

        sage: [statistic(graphs.CycleGraph(r)) for r in range(2,8)]
        [1, 3, 3, 3, 3, 3]

        sage: [statistic(graphs.StarGraph(r)) for r in range(2,8)]
        [2, 3, 4, 5, 6, 7]

        sage: [statistic(graphs.CompleteGraph(r)) for r in range(2,6)]
        [1, 3, 5, 6]

    See "The game chromatic index of wheels", Andres, Hochstättler,
    Schallück::

        sage: [statistic(graphs.WheelGraph(r)) for r in range(2,7)]
        [1, 3, 5, 5, 6]

        sage: statistic(graphs.PetersenGraph())

    """
    G = G.relabel(immutable=True, inplace=False)
    if G.num_edges() == 0:
        return 0
    for k in range(G.chromatic_index(), 2*max(G.degree())):
        if Alice_wins(G, k):
            return k

def normalize_colours(D):
    """
    From left to right, use small colours first.
    """
    pi = [None]*(max([v for v in D if v is not None])+1)
    i = 0
    for e in D:
        if e is not None and pi[e] is None:
            pi[e] = i
            i += 1
    return tuple([None if e is None else pi[e] for e in D])

@cached_function
def Alice_wins(G, k, C=None, E=None):
    """Return whether C is a winning position for Alice, who wants to
    properly color the graph.

    Expect that the vertices are labelled 0,1,...

    """
    def children(D):
        if all(c is None for c in D):
            colours = 1
        else:
            colours = min(k, max(v for v in D if v is not None)+2)
        for i in range(m):
            if D[i] is None:
                e = E[i]
                for d in range(colours):
                    if not any(i != j and D[j] == d and (E[j][0] in e or E[j][1] in e) for j in range(m)):
                        yield D[:i] + tuple([d]) + D[i+1:]

    if C is None:
        C = tuple([None]*G.num_edges())

    if E is None:
        E = tuple(G.edges(labels=False))
    m = len(E)
    
    uncoloured_edges = C.count(None)
    if uncoloured_edges == 0:
        return True
    # let Alice colour an edge
    for A in children(C):
        # if C was missing precisely one edge, and we could
        # colour it, Alice wins
        if uncoloured_edges == 1:
            return True
        # Alice wins if there is a D such that all moves of Bob make Alice win
        has_colouring = False
        for B in children(A):
            has_colouring = True
            if not Alice_wins(G, k, normalize_colours(B), E):
                break
        else:
            if has_colouring:
                return True
    return False