edit this statistic or download as text // json
Identifier
Values
=>
Cc0020;cc-rep
([],1)=>0 ([],2)=>0 ([(0,1)],2)=>0 ([],3)=>0 ([(1,2)],3)=>0 ([(0,2),(1,2)],3)=>0 ([(0,1),(0,2),(1,2)],3)=>1 ([],4)=>0 ([(2,3)],4)=>0 ([(1,3),(2,3)],4)=>0 ([(0,3),(1,3),(2,3)],4)=>0 ([(0,3),(1,2)],4)=>0 ([(0,3),(1,2),(2,3)],4)=>0 ([(1,2),(1,3),(2,3)],4)=>1 ([(0,3),(1,2),(1,3),(2,3)],4)=>1 ([(0,2),(0,3),(1,2),(1,3)],4)=>0 ([(0,2),(0,3),(1,2),(1,3),(2,3)],4)=>1 ([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4)=>2 ([],5)=>0 ([(3,4)],5)=>0 ([(2,4),(3,4)],5)=>0 ([(1,4),(2,4),(3,4)],5)=>0 ([(0,4),(1,4),(2,4),(3,4)],5)=>0 ([(1,4),(2,3)],5)=>0 ([(1,4),(2,3),(3,4)],5)=>0 ([(0,1),(2,4),(3,4)],5)=>0 ([(2,3),(2,4),(3,4)],5)=>1 ([(0,4),(1,4),(2,3),(3,4)],5)=>0 ([(1,4),(2,3),(2,4),(3,4)],5)=>1 ([(0,4),(1,4),(2,3),(2,4),(3,4)],5)=>1 ([(1,3),(1,4),(2,3),(2,4)],5)=>0 ([(0,4),(1,2),(1,3),(2,4),(3,4)],5)=>0 ([(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>1 ([(0,4),(1,3),(2,3),(2,4),(3,4)],5)=>1 ([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>1 ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5)=>0 ([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>1 ([(0,4),(1,3),(2,3),(2,4)],5)=>0 ([(0,1),(2,3),(2,4),(3,4)],5)=>1 ([(0,3),(1,2),(1,4),(2,4),(3,4)],5)=>1 ([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5)=>2 ([(0,3),(0,4),(1,2),(1,4),(2,3)],5)=>1 ([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5)=>1 ([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5)=>2 ([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5)=>1 ([(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2 ([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2 ([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>2 ([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5)=>1 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5)=>2 ([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>3 ([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5)=>4 ([],6)=>0 ([(4,5)],6)=>0 ([(3,5),(4,5)],6)=>0 ([(2,5),(3,5),(4,5)],6)=>0 ([(1,5),(2,5),(3,5),(4,5)],6)=>0 ([(0,5),(1,5),(2,5),(3,5),(4,5)],6)=>0 ([(2,5),(3,4)],6)=>0 ([(2,5),(3,4),(4,5)],6)=>0 ([(1,2),(3,5),(4,5)],6)=>0 ([(3,4),(3,5),(4,5)],6)=>1 ([(1,5),(2,5),(3,4),(4,5)],6)=>0 ([(0,1),(2,5),(3,5),(4,5)],6)=>0 ([(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,5),(2,5),(3,4),(4,5)],6)=>0 ([(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(2,4),(2,5),(3,4),(3,5)],6)=>0 ([(0,5),(1,5),(2,4),(3,4)],6)=>0 ([(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>0 ([(0,5),(1,5),(2,3),(3,4),(4,5)],6)=>0 ([(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,5),(2,4),(3,4),(4,5)],6)=>0 ([(0,5),(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>0 ([(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>0 ([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>0 ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>0 ([(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>0 ([(0,4),(0,5),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,4),(2,3)],6)=>0 ([(1,5),(2,4),(3,4),(3,5)],6)=>0 ([(0,1),(2,5),(3,4),(4,5)],6)=>0 ([(1,2),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,4),(2,3),(3,5),(4,5)],6)=>0 ([(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>1 ([(0,1),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>1 ([(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>2 ([(0,5),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>2 ([(1,4),(1,5),(2,3),(2,5),(3,4)],6)=>1 ([(0,5),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>0 ([(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,2),(1,4),(2,3),(3,5),(4,5)],6)=>1 ([(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,5),(1,4),(2,3),(2,4),(3,5)],6)=>0 ([(0,1),(2,4),(2,5),(3,4),(3,5)],6)=>0 ([(0,5),(1,5),(2,3),(2,4),(3,4)],6)=>1 ([(0,4),(1,2),(1,3),(2,5),(3,5),(4,5)],6)=>0 ([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5)],6)=>1 ([(0,4),(1,2),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,1),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,4),(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>1 ([(0,3),(0,4),(1,2),(1,5),(2,5),(3,5),(4,5)],6)=>1 ([(0,3),(1,4),(1,5),(2,4),(2,5),(3,5),(4,5)],6)=>1 ([(0,4),(1,2),(1,5),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,1),(0,5),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>1 ([(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>1 ([(0,3),(0,5),(1,3),(1,5),(2,4),(2,5),(3,4),(4,5)],6)=>1 ([(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>2 ([(0,1),(0,5),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>1 ([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>1 ([(0,4),(0,5),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,5),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>0 ([(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>1 ([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>1 ([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2 ([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2 ([(0,4),(0,5),(1,2),(1,3),(2,5),(3,4)],6)=>0 ([(0,3),(0,5),(1,2),(1,5),(2,4),(3,4),(4,5)],6)=>0 ([(0,5),(1,2),(1,4),(2,3),(3,4),(3,5),(4,5)],6)=>1 ([(0,1),(0,2),(1,5),(2,4),(3,4),(3,5),(4,5)],6)=>1 ([(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>1 ([(0,5),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5)],6)=>1 ([(0,1),(0,5),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,4),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,5),(4,5)],6)=>2 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2 ([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5)],6)=>0 ([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(3,5),(4,5)],6)=>1 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>1 ([(0,4),(0,5),(1,2),(1,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,5),(1,2),(1,3),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(0,5),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(0,4),(0,5),(1,2),(1,4),(2,3),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>3 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5)],6)=>0 ([(0,1),(0,2),(0,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>1 ([(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>2 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>2 ([(0,3),(0,4),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(0,4),(0,5),(1,2),(1,3),(2,3),(4,5)],6)=>2 ([(0,2),(1,4),(1,5),(2,3),(3,4),(3,5),(4,5)],6)=>1 ([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(4,5)],6)=>2 ([(0,1),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,1),(0,5),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>2 ([(0,1),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,1),(0,5),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(0,4),(0,5),(1,2),(1,3),(2,3),(2,5),(3,4),(4,5)],6)=>2 ([(0,4),(0,5),(1,2),(1,3),(1,4),(2,3),(2,5),(3,5),(4,5)],6)=>2 ([(0,3),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,3),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>2 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4)],6)=>1 ([(0,1),(0,5),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>2 ([(0,3),(0,4),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>2 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,5),(4,5)],6)=>3 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,5),(3,4)],6)=>2 ([(0,1),(0,3),(0,5),(1,2),(1,4),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>3 ([(0,1),(0,4),(0,5),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4 ([(0,2),(0,5),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(3,5),(4,5)],6)=>2 ([(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,4),(0,5),(1,2),(1,3),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(0,5),(1,2),(1,3),(1,4),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>3 ([(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4 ([(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4 ([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4 ([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4 ([(0,3),(0,4),(0,5),(1,2),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3 ([(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5)],6)=>3 ([(0,1),(0,4),(0,5),(1,2),(1,3),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>2 ([(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,5),(4,5)],6)=>3 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)],6)=>4 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>4 ([(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>5 ([(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)],6)=>6
search for individual values
searching the database for the individual values of this statistic
/ search for generating function
searching the database for statistics with the same generating function
click to show known generating functions       
Description
The minimal number of edges to remove to make a graph bipartite.
Code
@cached_function
def graph_of_graphs(n):
    """
    sage: H = graph_of_graphs(4)
    sage: H.relabel(lambda g: tuple(g.edges(labels=False)))
    sage: H.show()
    """
    lg1 = [(i, g.canonical_label().copy(immutable=True)) for i, g in enumerate(graphs(n))]
    lg2 = {g: i for i, g in lg1}
    lg1 = dict(lg1)
    H = Graph(len(lg1))
    for g in lg2:
        h = g.copy(immutable=False)
        for e in g.edges(labels=False):
            h.delete_edge(e)
            g2 = h.copy().canonical_label().copy(immutable=true)
            H.add_edge([lg2[g], lg2[g2]])
            h.add_edge(e)
    H.relabel(lambda i: lg1[i])
    return H

def statistic(g):
    mn = g.num_verts()
    G = graph_of_graphs(g.num_verts())
    g = g.canonical_label().copy(immutable=True)
    for h in G.vertices(sort=False):
        if h.is_bipartite():
            mn = min(mn, G.shortest_path_length(g, h))
            if mn == 0:
                return mn
    return mn
Created
Jul 23, 2020 at 12:52 by Martin Rubey
Updated
Dec 23, 2020 at 11:54 by Martin Rubey