"""
On the dimension of a graph, Paul Erdös, Frank Harary and William
T. Tutte
"""

dimensions = dict()
N = 7
for n in range(1,N+1):
    # C_n
    if n > 3:
        G = graphs.CycleGraph(n)
        dimensions[G.canonical_label().copy(immutable=True)] = 2
    # P_n
    if n > 1:
        G = graphs.PathGraph(n)
        dimensions[G.canonical_label().copy(immutable=True)] = 1
    # K_n
    G = graphs.CompleteGraph(n)
    dimensions[G.canonical_label().copy(immutable=True)] = n-1
    # K_n-e
    if n > 2:
        G.delete_edge(G.edges()[0])
        dimensions[G.canonical_label().copy(immutable=True)] = n-2

    # K_{2,n}
    G = graphs.CompleteBipartiteGraph(2, n)
    if n >= 3:
        dimensions[G.canonical_label().copy(immutable=True)] = 3
    elif n == 2:
        dimensions[G.canonical_label().copy(immutable=True)] = 2
    # K_{3,n}
    G = graphs.CompleteBipartiteGraph(3, n)
    if n >= 3:
        dimensions[G.canonical_label().copy(immutable=True)] = 4

    # Wheel
    G = graphs.WheelGraph(n) # n vertices
    if n in [5, 6]:
        dimensions[G.canonical_label().copy(immutable=True)] = 3
    elif n == 7:
        dimensions[G.canonical_label().copy(immutable=True)] = 2
    elif n > 7:
        dimensions[G.canonical_label().copy(immutable=True)] = 3
    G = graphs.CubeGraph(n) # 2^n vertices
    if n > 1:
        dimensions[G.canonical_label().copy(immutable=True)] = 2

def statistic(G):
    global dimensions
    # bridges do not change the dimension, unless we have a forest
    G = G.copy(immutable=False)
    bridges = list(G.bridges())
    if G.num_edges() == len(bridges):
        if G.num_edges() == 0:
            return 0
        if max(G.degree()) <= 2:
            return 1
        return 2
    G.delete_edges(bridges)
    l = G.connected_components_subgraphs()
    if len(l) > 1:
        statistics = [statistic(H) for H in l]
        if not any(v is None for v in statistics):
            return max(statistics)
    l = G.blocks_and_cut_vertices()[0]
    if len(l) > 1:
        statistics = [statistic(G.subgraph(B)) for B in l]
        if not any(v is None for v in statistics):
            return max(statistics)
    G = G.canonical_label().copy(immutable=True)
    if G in dimensions:
        return dimensions[G]
    n = G.num_verts()
    if G.is_clique():
        return n-1