Sharedgt.sageOpen in CoCalc
#GRAPH UTILITIES

def check_independence_extension(g,S):
    """
    Returns True if the set S extends to a maximum independent set of the graph g.

        sage: check_independence_extension(graphs.CycleGraph(6), Set([0,2]))
        True
        sage: check_independence_extension(graphs.CycleGraph(6), Set([0,3]))
        False
    """
    V = g.vertices()
    alpha = g.independent_set(value_only=True)
    #print alpha

    if not S.issubset(Set(V)) or not g.is_independent_set(S):
        return False

    N = neighbors_set(g,S)
    X = [v for v in V if v not in S and v not in N]
    h = g.subgraph(X)
    alpha_h = h.independent_set(value_only=True)
    #print alpha_h, len(S)

    return (alpha == alpha_h + len(S))

def find_alpha_critical_graphs(order, save = False):
    """
    Returns a list of the graph6 string of each of the alpha critical graphs of
    the given order. A graph g is alpha critical if alpha(g-e) > alpha(g) for
    every edge e in g. This looks at every graph of the given order, so this
    will be slow for any order larger than 8.
    If save = True (default False), then list will be saved to a file
    named "alpha_critical_name_list_{order}".

    There is a unique alpha critical graph on 3 and 4 vertices::

        sage: find_alpha_critical_graphs(3)
        ['Bw']
        sage: find_alpha_critical_graphs(4)
        ['C~']

    There are two alpha critical graphs on 5 vertices::

        sage: find_alpha_critical_graphs(5)
        ['Dhc', 'D~{']

    There are two alpha critical graphs on 6 vertices::

        sage: find_alpha_critical_graphs(6)
        ['E|OW', 'E~~w']
    """
    graphgen = graphs(order)
    alpha_critical_name_list = []
    for g in graphgen:
        if g.is_connected():
            if is_alpha_critical(g):
                alpha_critical_name_list.append(g.graph6_string())
    s = "alpha_critical_name_list_{}".format(order)
    if save:
        save(alpha_critical_name_list, s)
    return alpha_critical_name_list

def is_degree_sequence(L):
    """
    Returns True if the list L is the degree sequence of some graph.

    Since a graph always contains at least two vertices of the same degree, a
    list containing no duplicates cannot be a degree sequence::

        sage: is_degree_sequence([i for i in range(8)])
        False

    A cycle has all degrees equal to two and exists for any order larger than
    3, so a list of twos of length at least 3 is a degree sequence::

        sage: is_degree_sequence([2]*10)
        True
    """
    try:
        graphs.DegreeSequence(L)
    except:
        return False
    return True

#ALPHA APPROXIMATIONS

def find_lower_bound_sets(g, i):
    """
    Returns a list of independent sets of size i unioned with their neighborhoods.
    Since this checks all subsets of size i, this is a potentially slow method!

        sage: l = find_lower_bound_sets(graphs.CycleGraph(6),2)
        sage: l
        [{0, 1, 2, 3, 5},
         {0, 1, 2, 3, 4, 5},
         {0, 1, 3, 4, 5},
         {0, 1, 2, 3, 4},
         {0, 1, 2, 4, 5},
         {1, 2, 3, 4, 5},
         {0, 2, 3, 4, 5}]
        sage: type(l[0])
        <class 'sage.sets.set.Set_object_enumerated_with_category'>
    """
    V = g.vertices()
    lowersets = []

    for S in Subsets(Set(V),i):
        if g.is_independent_set(S):
            T = Set(closed_neighborhood(g,list(S)))
            if T not in Set(lowersets):
                lowersets.append(T)
    return lowersets

def alpha_lower_approximation(g, i):
    LP = MixedIntegerLinearProgram(maximization=False)
    x = LP.new_variable(nonnegative=True)

    # We define the objective
    LP.set_objective(sum([x[v] for v in g]))

    # For any subset, we define a constraint
    for j in range(1,i+1):
        for S in find_lower_bound_sets(g, j):
            #print S, S.cardinality()

            LP.add_constraint(sum([x[k] for k in S]), min = j)

    LP.solve()

    #return LP

    x_sol = LP.get_values(x)
    print x_sol
    return sum(x_sol.values())

#input = graph g
#output = bipartite graph with twice as many nodes and edges
#new nodes are labeled n to 2n-1
#assumes nodes in g are labeled [0..n-1]
#same as cartesian product with k2, but output labeling is guarnateed to be integers
def make_bidouble_graph(g):
    n = g.order()
    gdub = Graph(2*n)
    #print "gdub order = {}".format(gdub.order())

    for (i,j) in g.edges(labels = False):
        #print (i,j)
        gdub.add_edge(i,j+n)
        gdub.add_edge(j,i+n)
    return gdub

def neighbors_set(g,S):
    N = set()
    for v in S:
        for n in g.neighbors(v):
            N.add(n)
    return list(N)

def closed_neighborhood(g, verts):
    if isinstance(verts, list):
        neighborhood = []
        for v in verts:
            neighborhood += [v] + g.neighbors(v)
        return list(set(neighborhood))
    else:
        return [verts] + g.neighbors(verts)

def is_alpha_critical(g):
    #if not g.is_connected():
        #return False
    alpha = g.independent_set(value_only=True)
    for e in g.edges():
        gc = copy(g)
        gc.delete_edge(e)
        alpha_prime = gc.independent_set(value_only=True)
        if alpha_prime <= alpha:
            return False
    return True

#HEURISTIC ALGORITHMS

#takes vertex of max degree, deletes so long as degree > 0, returns remaining ind set
def MAXINE_independence_heuristic(g):
    V = g.vertices()
    h = g.subgraph(V)
    delta = max(h.degree())

    while delta > 0:
        #print "V is {}".format(V)
        #print "h vertices = {}, h.degree = {}".format(h.vertices(),h.degree())

        max_degree_vertex = V[h.degree().index(delta)]
        #print "max_degree_vertex = {}".format(max_degree_vertex)
        #print "h.neighbors(max_degree_vertex) = {}".format(h.neighbors(max_degree_vertex))
        V.remove(max_degree_vertex)
        h = g.subgraph(V)
        delta = max(h.degree())
        print "delta = {}".format(delta)

    return len(V)

#takes vertex of min degree, adds it to max ind set until no vertices left
def MIN_independence_heuristic(g):
    V = g.vertices()
    I = []
    while V != []:
        #print "V is {}".format(V)
        h = g.subgraph(V)
        #print "h vertices = {}, h.degree = {}".format(h.vertices(),h.degree())
        delta = min(h.degree())
        #print "delta = {}".format(delta)
        min_degree_vertex = V[h.degree().index(delta)]
        #print "min_degree_vertex = {}".format(min_degree_vertex)
        I.append(min_degree_vertex)
        V = [v for v in V if v not in closed_neighborhood(h, min_degree_vertex)]
        #break
    return len(I)

"""
Returns true if the given graph exists in the given list.
It also prints out all graphs in the list that are isomorphic so that duplicates may also be found here.
"""
def does_graph_exist(g, L):
    success = False
    for gL in L:
        if g.is_isomorphic(gL):
            print gL.name()
            success = True
    return success

"""
Returns a list of all pairs of isomorphic graphs in the given list.
"""
import itertools
def find_isomorphic_pairs(l):
    pairs = []
    L = itertools.combinations(l, r = 2)
    for pair in L:
        if pair[0].is_isomorphic(pair[1]):
            pairs.append(pair)
    return pairs

def find_all_max_ind_sets(g):
    """
    Finds all the maximum independent sets and stores them in a list
    """
    final_list = []
    V = Set(g.vertices())
    alpha = independence_number(g)

    for s in V.subsets(alpha):
        if g.is_independent_set(s):
            final_list.append(s)

    return final_list

def add_to_lists(graph, *L):
    """
    Adds the specified graph to the arbitrary number of lists given as the second through last argument
    Use this function to build the lists of graphs
    """
    for list in L:
            list.append(graph)

def MIR(n):
    if n < 2:
        raise RuntimeError("MIR is defined for n >= 2")
    if n % 2 == 0:
        g = graphs.PathGraph(2)
    else:
        g = graphs.PathGraph(3)
    while g.order() < n:
        new_v = g.add_vertex()
        for v in g.vertices():
            if v != new_v:
                g.add_edge(v, new_v)
        g.add_edge(new_v, g.add_vertex())
    return g

def Ciliate(q, r):
    if q < 1:
        raise RuntimeError("q must be greater than or equal to 1")
    if r < q:
        raise RuntimeError("r must be greater than or equal to q")
    if q == 1:
        return graphs.PathGraph(2*r)
    if q == r:
        return graphs.CycleGraph(2*q)
    g = graphs.CycleGraph(2*q)
    for v in g.vertices():
        g.add_path([v]+[g.add_vertex() for _ in range(r-q)])
    return g

def Antihole(n):
    if n < 5:
        raise RuntimeError("antihole is defined for n > 5")
    return graphs.CycleGraph(n).complement()

def Caro_Roditty(n):
    """
    p.171
    Caro, Y., and Y. Roditty. "On the vertex-independence number and star decomposition of graphs." Ars Combinatoria 20 (1985): 167-180.
    """
    g = graphs.CycleGraph(4)
    iters = 1
    while iters < n:
        len_v = len(g.vertices())
        g.add_cycle(range(len_v, len_v + 4))
        last_cycle = g.vertices()[-4:]
        for v in last_cycle:
            g.add_edge(v, v-4)
        iters += 1
    return g

def find_all_triangles(g):
    E = g.edges()
    A = g.adjacency_matrix()
    pos = {v:p for (p,v) in enumerate(g.vertices())}
    triangles = []

    for e in E:
        v,w = (e[0], e[1]) if pos[e[0]] < pos[e[1]] else (e[1], e[0])
        S = [u for u in g.vertices() if g.has_edge(u,v) and g.has_edge(u,v) and pos[u] > pos[w]]
        for u in S:
            s = Set([u,v,w])
            triangles.append(s)
    return triangles

# the triangles of a graph g are the vertices of the returned auxilliary graph aux_g
# with edges in aux_g between a pair of vertices in aux_g if the corresponding triangles share a vertex of g
def form_triangles_graph(g):
    vertices = find_all_triangles(g)
    edges = []
    for i in range(len(vertices)-1):
        for j in range(i+1, len(vertices)):
            if not((vertices[i].intersection(vertices[j])).is_empty()):
                edges.append((vertices[i],vertices[j]))
    return Graph([vertices,edges])

def max_bipartite_set(g,s,c):
    #print "s is {}".format(s)
    #print "c is {}".format(c)
    if len(c) == 0:
        return s

    v = c[0]
    #print "v is {}".format(v)
    SCopy = copy(s)
    SCopy.append(v)
    Gprime = g.subgraph(SCopy)

    CCopy = copy(c)
    CCopy.remove(v) #CCopy is C with v removed
    if not(Gprime.is_bipartite()):
        #print "{} is not bipartite".format(SCopy)
        return max_bipartite_set(g, s, CCopy)


    temp1 = max_bipartite_set(g, SCopy, CCopy)
    temp2 = max_bipartite_set(g, s, CCopy)

    if len(temp1) > len(temp2):
        return temp1
    else:
        return temp2

# output = closure of input graph
# Useful: a graph is hamiltonian iff its closure is hamiltonian
def closure(graph):
    """
    Test cases:
        sage: closure(graphs.CycleGraph(4)).is_isomorphic(graphs.CompleteGraph(4))
        True
        sage: closure(graphs.CycleGraph(5)).is_isomorphic(graphs.CycleGraph(5))
        True
    """
    from itertools import combinations
    g = graph.copy()
    while(True):
        flag = False
        deg = g.degree()
        for (v,w) in combinations(g.vertices(), 2):
            if (not g.has_edge(v,w)) and deg[v] + deg[w] >= g.order():
                g.add_edge(v,w)
                flag = True
        if flag == False:
            break
    return g

def is_simplical_vertex(g, v):
    """
    Vertex v is a simplical vertex in g if the induced neighborhood of v is a clique
    """
    neighbors = g.neighbors(v)
    induced_neighborhood = g.subgraph(neighbors)
    return induced_neighborhood.is_clique()

# Defined by Sergey Norin at SIAM DM 2018
def is_homogenous_set(g, s):
    """
    Set of vertices s is homogenous if s induces a clique or s is an independent set.
    """
    induced_g = g.subgraph(s)
    return g.is_independent_set(s) or induced_g.is_clique()

def generalized_degree(g,S):
    """
    The cardinality of the union of the neighborhoods of each v in S.
    """
    neighborhood_union = set(w for v in S for w in g.neighbors(v))
    return len(neighborhood_union)

def common_neighbors_of_set(g, s):
    """
    Returns the vertices in g adjacent to every vertex in s
    """
    if not s:
        return []
    comm_neigh = set(g.neighbors(s[0]))
    for v in s[1:]:
        comm_neigh = comm_neigh.intersection(set(g.neighbors(v)))
    return list(comm_neigh)

def common_neighbors(g, v, w):
    """
    returns the Set of common neighbors of v and w in graph g
        sage: common_neighbors(p4, 0, 3)
        {}
        sage: common_neighbors(p4, 0, 2)
        {1}
    """
    Nv = Set(g.neighbors(v))
    Nw = Set(g.neighbors(w))
    return Nv.intersection(Nw)

def extremal_triangle_free_extension(g):
    """
    Returns graph with edges added until no more possible without creating triangles.
    If input is not triangle-free, raises RuntimeError.

    This function is not deterministic; the output may vary among any of possibly many extremal triangle-free extensions.
    The output is also not necessarily the maximal triangle-free extension.
    """
    if not g.is_triangle_free():
        raise RuntimeError("Graph is not triangle-free")

    g2 = g.copy()
    from itertools import combinations
    for (v,w) in combinations(sample(g2.vertices(), k = g2.order()), 2): # Sample so output not deterministic
        if not g2.has_edge(v, w) and all(u not in g2.neighbors(v) for u in g2.neighbors(w)):
            g2.add_edge(v, w)
    return g2

def pyramid_encapsulation(g):
    """
    Returns the pyramid encapsulation of graph g.

    Let a pyramid be a triangle with each edge bisected, and the midpoints
        joined to form an inner triangle on vertices 0,1,2
    For any graph g, make all its vertices adjacent to 0,1,2.

    The pyramid is a pebbling Class1 graph (pebbling number is order + 1).
    The pyramid encapuslation always yields a Class1 graph.
    """
    pyramid = graphs.CompleteGraph(3)
    pyramid.add_vertices([3, 4, 5])
    pyramid.add_edges([[3,1], [3,0], [4,1], [4,2], [5,0], [5,2]])

    pe = pyramid.disjoint_union(g)
    for v in [0, 1, 2]:
        for w in g.vertices():
            pe.add_edge((0, v), (1,w))
    return pe

def cycle_lengths(g):
    """
    Returns set of all cycle lengths in g - without repetition

    If g is acyclic, returns an empty list.
    Performs depth-first search of all possible cycles.
    """
    lengths = set()
    for init_vertex in g.vertices():
        path_stack = [[init_vertex]]
        while path_stack:
            path = path_stack.pop()
            for neighbor in g.neighbors(path[-1]):
                if neighbor not in path:
                    path_stack.append(path + [neighbor])
                elif neighbor == path[0] and len(path) > 2:
                    lengths.add(len(path))
    return lengths

def max_induced_tree(g):
    """
    Returns *a* maximum-size tree which is an induced subgraph of g

    Raises ValueError if g is not connected, since some invariant theorems assume connected.
    """
    if not g.is_connected():
        raise ValueError("Input graph is not connected")

    from itertools import combinations
    for j in xrange(g.order()):
        for subset in combinations(sample(g.vertices(), k = g.order()), j): # randomize so avg.-case time, not worst-case
            sub_g = g.copy()
            sub_g.delete_vertices(subset)
            if sub_g.is_tree():
                return sub_g

def max_induced_forest(g):
    """
    Returns *a* maximum-size induced subgraph of g which is a forest

    Accepts both connected and disconnected graphs as input.
    """
    from itertools import combinations
    for j in xrange(g.order()):
        for subset in combinations(sample(g.vertices(), k = g.order()), j): # randomize so avg.-case time, not worst-case
            sub_g = g.copy()
            sub_g.delete_vertices(subset)
            if sub_g.is_forest():
                return sub_g

def is_matching(s):
    """
    True if set of edges s is a matching, i.e. no edges share a common vertex

    Ignores edges labels; only compares indices 0 and 1 in edge tuples.
    """
    vertex_list = [v for e in s for v in e[:2]] # Ignore any labels
    if len(vertex_list) != len(set(vertex_list)):
        return False
    else:
        return True

def mobius_ladder(k):
    """
    A mobius ladder with parameter k is a cubic graph on 2k vertices which can
    be constructed by taking a cycle on 2k vertices and connecting opposite
    vertices.

    sage: ml10 = mobius_ladder(10)
    sage: ml10
    mobius_ladder_10: Graph on 20 vertices
    sage: ml10.order()
    20
    sage: ml10.degree()
    [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
    sage: ml10.is_apex()
    True
    sage: ml10.is_vertex_transitive()
    True
    """
    g = graphs.CycleGraph(2*k)
    for i in range(k):
        g.add_edge(i, i+k)
    g.name(new = "mobius_ladder_{}".format(k))
    return g

def benoit_boyd_graphs(a, b, c):
    """
    Two triangles pointed at eachother, with opposite vertices connected by paths of a,b,c respective edges. Triangles weighted 0.5, paths 1.0.

    Pg. 927 of Geneviève Benoit and Sylvia Boyd, Finding the Exact Integrality Gap for Small Traveling Salesman Problems.
        Mathematics of Operations Research, 33(4): 921--931, 2008.
    """
    g = Graph(0, weighted = True)
    for i in xrange(0, a):
        g.add_edge(i, i + 1, 1)
    for i in xrange(a + 1, a + b + 1):
        g.add_edge(i, i + 1, 1)
    for i in xrange(a + b + 2, a + b + c + 2):
        g.add_edge(i, i + 1, 1)
    g.add_edges([(0, a + 1, 0.5), (a + 1, a + b + 2, 0.5), (0, a + b + 2, 0.5)])
    g.add_edges([(a, a + b + 1, 0.5), (a + b + 1, a + b + c + 2, 0.5), (a, a + b + c + 2, 0.5)])
    return g

def benoit_boyd_graphs_2(a, b, c):
    """
    Two triangles pointed at eachother, with opposite vertices connected by paths of a,b,c respective edges. Weights more complicated.

    Paths each weighted 1/a, 1/b, 1/c. The triangles are weighted with the sum of the paths they join, e.g. 1/a+1/b or 1/b+1/c.

    Pg. 928 of Geneviève Benoit and Sylvia Boyd, Finding the Exact Integrality Gap for Small Traveling Salesman Problems.
        Mathematics of Operations Research, 33(4): 921--931, 2008.
    """
    g = Graph(0, weighted = True)
    for i in xrange(0, a):
        g.add_edge(i, i + 1, 1/a)
    for i in xrange(a + 1, a + b + 1):
        g.add_edge(i, i + 1, 1/b)
    for i in xrange(a + b + 2, a + b + c + 2):
        g.add_edge(i, i + 1, 1/c)
    g.add_edges([(0, a + 1, 1/a + 1/b), (a + 1, a + b + 2, 1/b + 1/c), (0, a + b + 2, 1/a + 1/c)])
    g.add_edges([(a, a + b + 1, 1/a + 1/b), (a + b + 1, a + b + c + 2, 1/b + 1/c), (a, a + b + c + 2, 1/a + 1/c)])
    return g

def bipartite_double_cover(g):
    """
    Returns the bipatite double cover of a graph ``g``.

    From :wikipedia:`Bipartite double cover`:
    The bipartite double cover of ``g`` may also be known as the
    Kronecker double cover, canonical double cover or the bipartite double of G.
    For every vertex `v_i` of ``g``, there are two vertices `u_i` and `w_i`.
    Two vertices `u_i` and `w_j` are connected by an edge in the double cover if
    and only if `v_i` and `v_j` are connected by an edge in ``g``.

    EXAMPLES:

        sage: bipartite_double_cover(graphs.PetersenGraph()).is_isomorphic(graphs.DesarguesGraph())
        True

        sage: bipartite_double_cover(graphs.CycleGraph(4)).is_isomorphic(graphs.CycleGraph(4).disjoint_union(graphs.CycleGraph(4)))
        True
    """
    return g.tensor_product(graphs.CompleteGraph(2))

#TESTING

#check for invariant relation that separtates G from class defined by property
def find_separating_invariant_relation(g, objects, property, invariants):
    L = [x for x in objects if (property)(x)]
    for inv1 in invariants:
        for inv2 in invariants:
            if inv1(g) > inv2(g) and all(inv1(x) <= inv2(x) for x in L):
                return inv1.__name__, inv2.__name__
    print "no separating invariants"



#finds "difficult" graphs for necessary conditions, finds graphs which don't have property but which have all necessary conditions
def test_properties_upper_bound_theory(objects, property, theory):
     for g in objects:
         if not property(g) and all(f(g) for f in theory):
             print g.name()

#finds "difficult" graphs for sufficient conditions, finds graphs which dont have any sufficient but do have property
def test_properties_lower_bound_theory(objects, property, theory):
     for g in objects:
         if property(g) and not any(f(g) for f in theory):
             print g.name()

def find_coextensive_properties(objects, properties):
     for p1 in properties:
         for p2 in properties:
             if p1 != p2 and all(p1(g) == p2(g) for g in objects):
                 print p1.__name__, p2.__name__
     print "DONE!"

print("loaded utilities")

#############################################################################
# End of utilities section                                                  #
#############################################################################
#GRAPH INVARIANTS
all_invariants = []

efficient_invariants = []
intractable_invariants = []
theorem_invariants = []
broken_invariants = []

"""
    Last version of graphs packaged checked: Sage 8.2
    sage: sage.misc.banner.version_dict()['major'] < 8 or (sage.misc.banner.version_dict()['major'] == 8 and sage.misc.banner.version_dict()['minor'] <= 2)
    True
"""
sage_efficient_invariants = [Graph.number_of_loops, Graph.density, Graph.order, Graph.size, Graph.average_degree,
Graph.triangles_count, Graph.szeged_index, Graph.radius, Graph.diameter, Graph.girth, Graph.wiener_index,
Graph.average_distance, Graph.connected_components_number, Graph.maximum_average_degree, Graph.lovasz_theta,
Graph.spanning_trees_count, Graph.odd_girth, Graph.clustering_average, Graph.cluster_transitivity]

sage_intractable_invariants = [Graph.chromatic_number, Graph.chromatic_index, Graph.treewidth,
Graph.clique_number, Graph.pathwidth, Graph.fractional_chromatic_index, Graph.edge_connectivity,
Graph.vertex_connectivity, Graph.genus, Graph.crossing_number]

for i in sage_efficient_invariants:
    add_to_lists(i, efficient_invariants, all_invariants)
for i in sage_intractable_invariants:
    add_to_lists(i, intractable_invariants, all_invariants)

def distinct_degrees(g):
    """
    returns the number of distinct degrees of a graph
        sage: distinct_degrees(p4)
        2
        sage: distinct_degrees(k4)
        1
    """
    return len(set(g.degree()))
add_to_lists(distinct_degrees, efficient_invariants, all_invariants)

def max_common_neighbors(g):
    """
    Returns the maximum number of common neighbors of any pair of distinct vertices in g.

        sage: max_common_neighbors(p4)
        1
        sage: max_common_neighbors(k4)
        2
    """
    max = 0
    V = g.vertices()
    n = g.order()
    for i in range(n):
        for j in range(n):
            if i < j:
                temp = len(common_neighbors(g, V[i], V[j]))
                if temp > max:
                    max = temp
    return max
add_to_lists(max_common_neighbors, efficient_invariants, all_invariants)

def min_common_neighbors(g):
    """
    Returns the minimum number of common neighbors of any pair of distinct vertices in g,
    which is necessarily 0 for disconnected graphs.

        sage: min_common_neighbors(p4)
        0
        sage: min_common_neighbors(k4)
        2
    """
    n = g.order()
    min = n
    V = g.vertices()
    for i in range(n):
        for j in range(n):
            if i < j:
                temp = len(common_neighbors(g, V[i], V[j]))
                #if temp == 0:
                    #print "i={}, j={}".format(i,j)
                if temp < min:
                    min = temp
    return min
add_to_lists(min_common_neighbors, efficient_invariants, all_invariants)

def mean_common_neighbors(g):
    """
    Returns the average number of common neighbors of any pair of distinct vertices in g.
        sage: mean_common_neighbors(p4)
        1/3
        sage: mean_common_neighbors(k4)
        2
    """
    V = g.vertices()
    n = g.order()
    sum = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                sum += len(common_neighbors(g, V[i], V[j]))
    return 2*sum/(n*(n-1))
add_to_lists(mean_common_neighbors, efficient_invariants, all_invariants)

def min_degree(g):
    """
    Returns the minimum of all degrees of the graph g.

        sage: min_degree(graphs.CompleteGraph(5))
        4
        sage: min_degree(graphs.CycleGraph(5))
        2
        sage: min_degree(graphs.StarGraph(5))
        1
        sage: min_degree(graphs.CompleteBipartiteGraph(3,5))
        3
    """
    return min(g.degree())
add_to_lists(min_degree, efficient_invariants, all_invariants)

def max_degree(g):
    """
    Returns the maximum of all degrees of the graph g.

        sage: max_degree(graphs.CompleteGraph(5))
        4
        sage: max_degree(graphs.CycleGraph(5))
        2
        sage: max_degree(graphs.StarGraph(5))
        5
        sage: max_degree(graphs.CompleteBipartiteGraph(3,5))
        5
    """
    return max(g.degree())
add_to_lists(max_degree, efficient_invariants, all_invariants)

def median_degree(g):
    """
    Return the median of the list of vertex degrees.

        sage: median_degree(p4)
        3/2
        sage: median_degree(p3)
        1
    """
    return median(g.degree())
add_to_lists(median_degree, efficient_invariants, all_invariants)

def inverse_degree(g):
    """
    Return the sum of the reciprocals of the non-zero degrees.

    Return 0 if the graph has no edges.

        sage: inverse_degree(p4)
        3
        sage: inverse_degree(graphs.CompleteGraph(1))
        0
    """
    if g.size() == 0:
        return 0
    return sum([(1.0/d) for d in g.degree() if d!= 0])
add_to_lists(inverse_degree, efficient_invariants, all_invariants)

def eulerian_faces(g):
    """
    Returns 2 - order + size, which is the number of faces if the graph is planar,
    a consequence of Euler's Formula.

        sage: eulerian_faces(graphs.CycleGraph(5))
        2
        sage: eulerian_faces(graphs.DodecahedralGraph())
        12
    """
    n = g.order()
    m = g.size()
    return 2 - n + m
add_to_lists(eulerian_faces, efficient_invariants, all_invariants)

def barrus_q(g):
    """
    If the degrees sequence is in non-increasing order, with index starting at 1,
    barrus_q = max(k:d_k >= k)

    Defined by M. Barrus in "Havel-Hakimi Residues of Unigraphs", 2012

        sage: barrus_q(graphs.CompleteGraph(5))
        4
        sage: barrus_q(graphs.StarGraph(3))
        1
    """
    Degrees = g.degree()
    Degrees.sort()
    Degrees.reverse()
    return max(k for k in range(g.order()) if Degrees[k] >= (k+1)) + 1
add_to_lists(barrus_q, efficient_invariants, all_invariants)

def barrus_bound(g):
    """
    Returns n - barrus q

    Defined in: Barrus, Michael D. "Havel–Hakimi residues of unigraphs." Information Processing Letters 112.1 (2012): 44-48.

        sage: barrus_bound(k4)
        1
        sage: barrus_bound(graphs.OctahedralGraph())
        2
    """
    return g.order() - barrus_q(g)
add_to_lists(barrus_bound, efficient_invariants, all_invariants)

def matching_number(g):
    """
    Returns the matching number of the graph g, i.e., the size of a maximum
    matching.

    A matching is a set of independent edges.

    See: https://en.wikipedia.org/wiki/Matching_(graph_theory)

        sage: matching_number(graphs.CompleteGraph(5))
        2
        sage: matching_number(graphs.CycleGraph(5))
        2
        sage: matching_number(graphs.StarGraph(5))
        1
        sage: matching_number(graphs.CompleteBipartiteGraph(3,5))
        3
    """
    return int(g.matching(value_only=True, use_edge_labels=False))
add_to_lists(matching_number, efficient_invariants, all_invariants)

def residue(g):
    """
    If the Havel-Hakimi process is iterated until a sequence of 0s is returned,
    residue is defined to be the number of zeros of this sequence.

    See: Favaron, Odile, Maryvonne Mahéo, and J‐F. Saclé. "On the residue of a graph." Journal of Graph Theory 15.1 (1991): 39-64.

        sage: residue(k4)
        1
        sage: residue(p4)
        2
    """
    seq = g.degree_sequence()

    while seq[0] > 0:
        d = seq.pop(0)
        seq[:d] = [k-1 for k in seq[:d]]
        seq.sort(reverse=True)

    return len(seq)
add_to_lists(residue, efficient_invariants, all_invariants)

def annihilation_number(g):
    """
    Given the degree sequence in non-degreasing order, with indices starting at 1, the annihilation number is the largest index k so the sum of the first k degrees is no more than the sum of the remaining degrees

    See: Larson, Craig E., and Ryan Pepper. "Graphs with equal independence and annihilation numbers." the electronic journal of combinatorics 18.1 (2011): 180.

        sage: annihilation_number(c4)
        2
        sage: annihilation_number(p5)
        3
    """
    seq = sorted(g.degree())

    a = 0
    while sum(seq[:a+1]) <= sum(seq[a+1:]):
        a += 1

    return a
add_to_lists(annihilation_number, efficient_invariants, all_invariants)

def fractional_alpha(g):
    """
    This is the optimal solution of the linear programming relaxation of the integer programming formulation of independence number (alpha).

    See: Nemhauser, George L., and Leslie Earl Trotter. "Vertex packings: structural properties and algorithms." Mathematical Programming 8.1 (1975): 232-248.

        sage: fractional_alpha(k3)
        1.5
        sage: fractional_alpha(p5)
        3.0
    """
    if len(g.vertices()) == 0:
        return 0
    p = MixedIntegerLinearProgram(maximization=True)
    x = p.new_variable(nonnegative=True)
    p.set_objective(sum(x[v] for v in g.vertices()))

    for v in g.vertices():
        p.add_constraint(x[v], max=1)

    for (u,v) in g.edge_iterator(labels=False):
        p.add_constraint(x[u] + x[v], max=1)

    return p.solve()
add_to_lists(fractional_alpha, efficient_invariants, all_invariants)

def fractional_covering(g):
    """
    This is the optimal solution of the linear programming relaxation of the integer programming formulation of covering number.

    For ILP formulation see: https://en.wikipedia.org/wiki/Vertex_cover

        sage: fractional_covering(k3)
        1.5
        sage: fractional_covering(p5)
        2.0
    """
    if len(g.vertices()) == 0:
        return 0
    p = MixedIntegerLinearProgram(maximization=False)
    x = p.new_variable(nonnegative=True)
    p.set_objective(sum(x[v] for v in g.vertices()))

    for v in g.vertices():
        p.add_constraint(x[v], max=1)

    for (u,v) in g.edge_iterator(labels=False):
        p.add_constraint(x[u] + x[v], min=1)

    return p.solve()
add_to_lists(fractional_covering, efficient_invariants, all_invariants)

def cvetkovic(g):
    """
    This in the minimum of the number of nonnegative and nonpositive eigenvalues of the adjacency matrix.

    Cvetkovic's theorem says that this number is an upper bound for the independence number of a graph.

    See: Cvetković, Dragoš M., Michael Doob, and Horst Sachs. Spectra of graphs: theory and application. Vol. 87. Academic Pr, 1980.

        sage: cvetkovic(p5)
        3
        sage: cvetkovic(graphs.PetersenGraph())
        4
    """
    eigenvalues = g.spectrum()
    positive = 0
    negative = 0
    zero = 0
    for e in eigenvalues:
        if e > 0:
            positive += 1
        elif e < 0:
            negative += 1
        else:
            zero += 1

    return zero + min([positive, negative])
add_to_lists(cvetkovic, efficient_invariants, all_invariants)

def cycle_space_dimension(g):
    """
    Returns the dimension of the cycle space (also called the circuit rank).

    See: https://en.wikipedia.org/wiki/Cycle_space
    And: https://en.wikipedia.org/wiki/Circuit_rank

        sage: cycle_space_dimension(k3)
        1
        sage: cycle_space_dimension(c4c4)
        2
        sage: cycle_space_dimension(glasses_5_5)
        2
    """
    return g.size()-g.order()+g.connected_components_number()
add_to_lists(cycle_space_dimension, efficient_invariants, all_invariants)

def card_center(g):
    return len(g.center())
add_to_lists(card_center, efficient_invariants, all_invariants)

def card_periphery(g):
    return len(g.periphery())
add_to_lists(card_periphery, efficient_invariants, all_invariants)

def max_eigenvalue(g):
    return max(g.adjacency_matrix().change_ring(RDF).eigenvalues())
add_to_lists(max_eigenvalue, efficient_invariants, all_invariants)

def min_eigenvalue(g):
    return min(g.adjacency_matrix().change_ring(RDF).eigenvalues())
add_to_lists(min_eigenvalue, efficient_invariants, all_invariants)

def resistance_distance_matrix(g):
    L = g.laplacian_matrix()
    n = g.order()
    J = ones_matrix(n,n)
    temp = L+(1.0/n)*J
    X = temp.inverse()
    R = (1.0)*ones_matrix(n,n)
    for i in range(n):
        for j in range(n):
            R[i,j] = X[i,i] + X[j,j] - 2*X[i,j]
    return R

def kirchhoff_index(g):
    R = resistance_distance_matrix(g)
    return .5*sum(sum(R))
add_to_lists(kirchhoff_index, efficient_invariants, all_invariants)

def largest_singular_value(g):
    A = matrix(RDF,g.adjacency_matrix(sparse=False))
    svd = A.SVD()
    sigma = svd[1]
    return sigma[0,0]
add_to_lists(largest_singular_value, efficient_invariants, all_invariants)

def card_max_cut(g):
    return g.max_cut(value_only=True)
add_to_lists(card_max_cut, intractable_invariants, all_invariants)

def welsh_powell(g):
    """
    for degrees d_1 >= ... >= d_n
    returns the maximum over all indices i of of the min(i,d_i + 1)

    sage: welsh_powell(k5) = 4
    """
    n= g.order()
    D = g.degree()
    D.sort(reverse=True)
    mx = 0
    for i in range(n):
        temp = min({i,D[i]})
        if temp > mx:
            mx = temp
    return mx + 1
add_to_lists(welsh_powell, efficient_invariants, all_invariants)

#outputs upper bound from Brooks Theorem: returns Delta + 1 for complete and odd cycles
def brooks(g):
    Delta = max(g.degree())
    delta = min(g.degree())
    n = g.order()
    if is_complete(g):
        return Delta + 1
    elif n%2 == 1 and g.is_connected() and Delta == 2 and delta == 2: #same as if all degrees are 2
        return Delta + 1
    else:
        return Delta
add_to_lists(brooks, efficient_invariants, all_invariants)

#wilf's upper bound for chromatic number
def wilf(g):
    return max_eigenvalue(g) + 1
add_to_lists(wilf, efficient_invariants, all_invariants)

#a measure of irregularity
def different_degrees(g):
    return len(set(g.degree()))
add_to_lists(different_degrees, efficient_invariants, all_invariants)

def szekeres_wilf(g):
    """
    Returns 1+ max of the minimum degrees for all subgraphs
    Its an upper bound for chromatic number

    sage: szekeres_wilf(graphs.CompleteGraph(5))
    5
    """
    #removes a vertex, if possible, of degree <= i
    def remove_vertex_of_degree(gc,i):
        Dc = gc.degree()
        V = gc.vertices()
        #print "Dc is %s, V is %s" %(Dc,V)
        mind = min(Dc)
        #print "mind is %s" %mind
        if mind <= i:

            ind = Dc.index(mind)
            #print "ind is %s, vertex is %s" %(ind,V[ind])
            return gc.delete_vertex(V[ind])
        else:
            return gc
    D = g.degree()
    delta = min(D)
    Delta = max(D)
    for i in range(delta,Delta+1):
        gc = copy(g)
        value = g.order() + 1
        while gc.size() > 0 and gc.order() < value:
            #gc.show()
            value = gc.order()
            remove_vertex_of_degree(gc,i)
        if gc.size() == 0:
            return i + 1
add_to_lists(szekeres_wilf, efficient_invariants, all_invariants)

def average_vertex_temperature(g):
     D = g.degree()
     n = g.order()
     return sum([D[i]/(n-D[i]+0.0) for i in range(n)])/n
add_to_lists(average_vertex_temperature, efficient_invariants, all_invariants)

def sum_temperatures(g):
     D = g.degree()
     n = g.order()
     return sum([D[i]/(n-D[i]+0.0) for i in range(n)])
add_to_lists(sum_temperatures, efficient_invariants, all_invariants)

def randic(g):
     D = g.degree()
     V = g.vertices()
     if min(D) == 0:
          return oo
     sum = 0
     for e in g.edges():
         v = e[0]
         i = V.index(v)
         w = e[1]
         j = V.index(w)
         sum += 1.0/(D[i]*D[j])**0.5
     return sum
add_to_lists(randic, efficient_invariants, all_invariants)

#a very good lower bound for alpha
def max_even_minus_even_horizontal(g):
    """
    finds def max_even_minus_even_horizontal for each component and adds them up.
    """
    mx_even=0
    Gcomps=g.connected_components_subgraphs()

    while Gcomps != []:
            H=Gcomps.pop()
            temp=max_even_minus_even_horizontal_component(H)
            mx_even+=temp
            #print "temp = {}, mx_even = {}".format(temp,mx_even)

    return mx_even
add_to_lists(max_even_minus_even_horizontal, efficient_invariants, theorem_invariants, all_invariants)

def max_even_minus_even_horizontal_component(g):
    """
    for each vertex v, find the number of vertices at even distance from v,
    and substract the number of edges induced by these vertices.
    this number is a lower bound for independence number.
    take the max. returns 0 if graph is not connected
    """
    if g.is_connected()==False:
        return 0

    distances = g.distance_all_pairs()
    mx=0
    for v in g.vertices():
        Even=[]
        for w in g.vertices():
            if distances[v][w]%2==0:
                Even.append(w)

        #print len(Even), len(g.subgraph(Even).edges())
        l=len(Even)-len(g.subgraph(Even).edges())
        if l>mx:
            mx=l
    return mx

def laplacian_energy(g):
     L = g.laplacian_matrix().change_ring(RDF).eigenvalues()
     Ls = [1/lam**2 for lam in L if lam > 0]
     return 1 + sum(Ls)
add_to_lists(laplacian_energy, efficient_invariants, all_invariants)

def laplacian_energy_like(g):
    """
    Returns the sum of the square roots of the laplacian eigenvalues

    Liu, Jianping, and Bolian Liu. "A Laplacian-energy-like invariant of a graph." MATCH-COMMUNICATIONS IN MATHEMATICAL AND IN COMPUTER CHEMISTRY 59.2 (2008): 355-372.
    """
    return sum([sqrt(x) for x in g.spectrum(laplacian = True)])
add_to_lists(laplacian_energy_like, efficient_invariants, all_invariants)

#sum of the positive eigenvalues of a graph
def gutman_energy(g):
     L = g.adjacency_matrix().change_ring(RDF).eigenvalues()
     Ls = [lam for lam in L if lam > 0]
     return sum(Ls)
add_to_lists(gutman_energy, efficient_invariants, all_invariants)

#the second smallest eigenvalue of the Laplacian matrix of a graph, also called the "algebraic connectivity" - the smallest should be 0
def fiedler(g):
     L = g.laplacian_matrix().change_ring(RDF).eigenvalues()
     L.sort()
     return L[1]
add_to_lists(fiedler, broken_invariants, all_invariants)

def degree_variance(g):
     mu = mean(g.degree())
     s = sum((x-mu)**2 for x in g.degree())
     return s/g.order()
add_to_lists(degree_variance, efficient_invariants, all_invariants)

def graph_rank(g):
    return g.adjacency_matrix().rank()
add_to_lists(graph_rank, efficient_invariants, all_invariants)

def card_positive_eigenvalues(g):
    return len([lam for lam in g.adjacency_matrix().eigenvalues() if lam > 0])
add_to_lists(card_positive_eigenvalues, efficient_invariants, all_invariants)

def card_zero_eigenvalues(g):
    return len([lam for lam in g.adjacency_matrix().eigenvalues() if lam == 0])
add_to_lists(card_zero_eigenvalues, efficient_invariants, all_invariants)

def card_negative_eigenvalues(g):
    return len([lam for lam in g.adjacency_matrix().eigenvalues() if lam < 0])
add_to_lists(card_negative_eigenvalues, efficient_invariants, all_invariants)

def card_cut_vertices(g):
    return len((g.blocks_and_cut_vertices())[1])
add_to_lists(card_cut_vertices, efficient_invariants, all_invariants)

def card_connectors(g):
    return g.order() - card_cut_vertices(g)
add_to_lists(card_connectors, efficient_invariants, all_invariants)

#return number of leafs or pendants
def card_pendants(g):
    return sum([x for x in g.degree() if x == 1])
add_to_lists(card_pendants, efficient_invariants, all_invariants)

#returns number of bridges in graph
def card_bridges(g):
    gs = g.strong_orientation()
    bridges = []
    for scc in gs.strongly_connected_components():
        bridges.extend(gs.edge_boundary(scc))
    return len(bridges)
add_to_lists(card_bridges, efficient_invariants, all_invariants)

#upper bound for the domination number
def alon_spencer(g):
    delta = min(g.degree())
    n = g.order()
    return n*((1+log(delta + 1.0)/(delta + 1)))
add_to_lists(alon_spencer, efficient_invariants, all_invariants)

#lower bound for residue and, hence, independence number
def caro_wei(g):
    return sum([1.0/(d + 1) for d in g.degree()])
add_to_lists(caro_wei, efficient_invariants, all_invariants)

#equals 2*size, the 1st theorem of graph theory
def degree_sum(g):
    return sum(g.degree())
add_to_lists(degree_sum, efficient_invariants, all_invariants)

#smallest sum of degrees of non-adjacent degrees, invariant in ore condition for hamiltonicity
#default for complete graph?
def sigma_dist2(g):
    if g.size() == g.order()*(g.order()-1)/2:
        return g.order()
    Dist = g.distance_all_pairs()
    return min(g.degree(v) + g.degree(w) for v in g for w in g if Dist[v][w] > 1)
add_to_lists(sigma_dist2, efficient_invariants, all_invariants)

#cardinality of the automorphism group of the graph
def order_automorphism_group(g):
    return g.automorphism_group(return_group=False, order=True)
add_to_lists(order_automorphism_group, efficient_invariants, all_invariants)

#in sufficient condition for graphs where vizing's independence theorem holds
def brinkmann_steffen(g):
    E = g.edges()
    if len(E) == 0:
        return 0
    Dist = g.distance_all_pairs()
    return min(g.degree(v) + g.degree(w) for v in g for w in g if Dist[v][w] == 1)
add_to_lists(brinkmann_steffen, efficient_invariants, all_invariants)

def alpha_critical_optimum(g, alpha_critical_names):

    n = g.order()
    V = g.vertices()
    #g.show()

    alpha_critical_graph_names = []

    #get alpha_critical graphs with order <= n
    for name in alpha_critical_names:
        h = Graph(name)
        if h.order() <= n:
            alpha_critical_graph_names.append(h.graph6_string())

    #print alpha_critical_graphs

    LP = MixedIntegerLinearProgram(maximization=True)
    b = LP.new_variable(nonnegative=True)

    # We define the objective
    LP.set_objective(sum([b[v] for v in g]))

    # For any edge, we define a constraint
    for (u,v) in g.edges(labels=None):
        LP.add_constraint(b[u]+b[v],max=1)
        #LP.add_constraint(b[u]+b[v],min=1)

    #search through all subsets of g with order >= 3
    #and look for *any* subgraph isomorphic to an alpha critical graph
    #for any match we define a constraint

    i = 3
    while i <= n:
        SS = Subsets(Set(V),i)
        for S in SS:
            L = [g6 for g6 in alpha_critical_graph_names if Graph(g6).order() == i]
            #print L
            for g6 in L:
                h = Graph(g6)
                if g.subgraph(S).subgraph_search(h, induced=False):

                    #print S
                    #add constraint
                    alpha = independence_number(h)
                    #print h.graph6_string(), alpha
                    LP.add_constraint(sum([b[j] for j in S]), max = alpha, name = h.graph6_string())
        i = i + 1

    #for c in LP.constraints():
        #print c

    # The .solve() functions returns the objective value
    LP.solve()

    #return LP

    b_sol = LP.get_values(b)
    return b_sol, sum(b_sol.values())


###several invariants and auxiliary functions related to the Independence Decomposition Theorem

#finds all vertices with weight 1 in some max weighted stable set with wieghts in {0,1,1/2}
#had problem that LP solver has small numerical errors, fixed with kludgy if condition
def find_stable_ones_vertices(g):
    F = []
    alpha_f = fractional_alpha(g)
    for v in g.vertices():
        gc = copy(g)
        gc.delete_vertices(closed_neighborhood(gc, v))
        alpha_f_prime = fractional_alpha(gc)
        if abs(alpha_f - alpha_f_prime - 1) < .01:
            F.append(v)
    return F

def find_max_critical_independent_set(g):
    S = find_stable_ones_vertices(g)
    H = g.subgraph(S)
    return H.independent_set()

def critical_independence_number(g):
    return len(find_max_critical_independent_set(g))
add_to_lists(critical_independence_number, efficient_invariants, all_invariants)

def card_independence_irreducible_part(g):
    return len(find_independence_irreducible_part(g))
add_to_lists(card_independence_irreducible_part, efficient_invariants, all_invariants)

def find_independence_irreducible_part(g):
    X = find_KE_part(g)
    SX = Set(X)
    Vertices = Set(g.vertices())
    return list(Vertices.difference(SX))

#returns KE part guaranteed by Independence Decomposition Theorem
def find_KE_part(g):
    return closed_neighborhood(g, find_max_critical_independent_set(g))

def card_KE_part(g):
    return len(find_KE_part(g))
add_to_lists(card_KE_part, efficient_invariants, all_invariants)

def find_independence_irreducible_subgraph(g):
    return g.subgraph(find_independence_irreducible_part(g))

def find_KE_subgraph(g):
    return g.subgraph(find_KE_part(g))


#make invariant from property
def make_invariant_from_property(property, name=None):
    """
    This function takes a property as an argument and returns an invariant
    whose value is 1 if the object has the property, else 0
    Optionally a name for the new property can be provided as a second argument.
    """
    def boolean_valued_invariant(g):
        if property(g):
            return 1
        else:
            return 0

    if name is not None:
        boolean_valued_invariant.__name__ = name
    elif hasattr(property, '__name__'):
        boolean_valued_invariant.__name__ = '{}_value'.format(property.__name__)
    else:
        raise ValueError('Please provide a name for the new function')

    return boolean_valued_invariant

# defined by R. Pepper in an unpublished paper on graph irregularity
def geometric_length_of_degree_sequence(g):
    return sqrt(sum(d**2 for d in g.degree()))
add_to_lists(geometric_length_of_degree_sequence, efficient_invariants, all_invariants)

# Two Stability Theta Bound
# For graphs with alpha <= 2,
# lovasz_theta <= 2^(2/3)*n^(1/3)
# The Sandwich Theorem by Knuth p. 47
def two_stability_theta_bound(g):
    return 2**(2/3)*g.order()**(1/3)
add_to_lists(two_stability_theta_bound, efficient_invariants, all_invariants)

# Lovasz Theta over Root N
# The Sandwich Theorem by Knuth p. 45
def lovasz_theta_over_root_n(g):
    return g.lovasz_theta()/sqrt(g.order())
add_to_lists(lovasz_theta_over_root_n, efficient_invariants, all_invariants)

# Theta * Theta-Complement
# The Sandwich Theorem by Knuth, p. 27
def theta_theta_complement(g):
    return g.lovasz_theta() * g.complement().lovasz_theta()
add_to_lists(theta_theta_complement, efficient_invariants, all_invariants)

# Depth = Order - Residue
# This is the number of steps it takes for Havel-Hakimi to terminate
def depth(g):
    return g.order()-residue(g)
add_to_lists(depth, efficient_invariants, all_invariants)

# Lovasz Theta of the complement of the given graph
def lovasz_theta_complement(g):
    return g.complement().lovasz_theta()
add_to_lists(lovasz_theta_complement, efficient_invariants, all_invariants)

# N over lovasz_theta_complement
# This is a lower bound for lovasz theta
# The Sandwich Theorem by Knuth, p. 27
def n_over_lovasz_theta_complement(g):
    return g.order()/lovasz_theta_complement(g)
add_to_lists(n_over_lovasz_theta_complement, efficient_invariants, all_invariants)

# The number of vertices at even distance from v and return the max over all vertices
def max_even(g):
    from sage.graphs.distances_all_pairs import distances_all_pairs
    D = distances_all_pairs(g)
    evens_list = []
    for u in D:
        evens = 0
        for v in D[u]:
            if D[u][v] % 2 == 0:
                evens += 1
        evens_list.append(evens)
    return max(evens_list)
add_to_lists(max_even, efficient_invariants, all_invariants)

# The number of vertices at even distance from v and return the min over all vertices
def min_even(g):
    from sage.graphs.distances_all_pairs import distances_all_pairs
    D = distances_all_pairs(g)
    evens_list = []
    for u in D:
        evens = 0
        for v in D[u]:
            if D[u][v] % 2 == 0:
                evens += 1
        evens_list.append(evens)
    return min(evens_list)
add_to_lists(min_even, efficient_invariants, all_invariants)

# The number of vertices at odd distance from v and return the max over all vertices
def max_odd(g):
    from sage.graphs.distances_all_pairs import distances_all_pairs
    D = distances_all_pairs(g)
    odds_list = []
    for u in D:
        odds = 0
        for v in D[u]:
            if D[u][v] % 2 != 0:
                odds += 1
        odds_list.append(odds)
    return max(odds_list)
add_to_lists(max_odd, efficient_invariants, all_invariants)

# The number of vertices at odd distance from v and return the min over all vertices
def min_odd(g):
    from sage.graphs.distances_all_pairs import distances_all_pairs
    D = distances_all_pairs(g)
    odds_list = []
    for u in D:
        odds = 0
        for v in D[u]:
            if D[u][v] % 2 != 0:
                odds += 1
        odds_list.append(odds)
    return min(odds_list)
add_to_lists(min_odd, efficient_invariants, all_invariants)

#returns sum of distances between *distinct* vertices, return infinity is graph is not connected
def transmission(g):
    if not g.is_connected():
        return Infinity
    if g.is_tree() and max(g.degree()) == 2:
        summation = 0
        for i in range(1,g.order()):
            summation += (i*(i+1))/2
        return summation * 2
    else:
        V = g.vertices()
        D = g.distance_all_pairs()
        return sum([D[v][w] for v in V for w in V if v != w])
add_to_lists(transmission, efficient_invariants, all_invariants)

def harmonic_index(g):
    sum = 0
    for (u,v) in g.edges(labels = false):
        sum += (2 / (g.degree(u) + g.degree(v)))
    return sum
add_to_lists(harmonic_index, efficient_invariants, all_invariants)

def bavelas_index(g):
    """
    returns sum over all edges (v,w) of (distance from v to all other vertices)/(distance from w to all other vertices)
    computes each edge twice (once with v computation in numerator, once with w computation in numerator)

        sage: bavelas_index(p6)
        5086/495
        sage: bavelas_index(k4)
        12
    """
    D = g.distance_all_pairs()

    def s_aux(v):
        """
        computes sum of distances from v to all other vertices
        """
        sum = 0
        for w in g.vertices():
            sum += D[v][w]
        return sum

    sum_final = 0

    for edge in g.edges(labels=false):
        v = edge[0]
        w = edge[1]
        sum_final += (s_aux(w) / s_aux(v)) + (s_aux(v) / s_aux(w))

    return sum_final
add_to_lists(bavelas_index, efficient_invariants, all_invariants)

#a solution of the invariant interpolation problem for upper bound of chromatic number for c8chords
#all upper bounds in theory have value at least 3 for c8chords
#returns 2 for bipartite graphs, order for non-bipartite
def bipartite_chromatic(g):
    if g.is_bipartite():
        return 2
    else:
        return g.order()
add_to_lists(bipartite_chromatic, efficient_invariants, all_invariants)

def beauchamp_index(g):
    """
    Defined on page 597 of Sabidussi, Gert. "The centrality index of a graph." Psychometrika 31.4 (1966): 581-603.

    sage: beauchamp_index(c4)
    1
    sage: beauchamp_index(p5)
    137/210
    sage: beauchamp_index(graphs.PetersenGraph())
    2/3
    """

    D = g.distance_all_pairs()

    def s_aux(v): #computes sum of distances from v to all other vertices
        sum = 0
        for w in g.vertices():
            sum += D[v][w]
        return sum

    sum_final = 0

    for v in g.vertices():
        sum_final += 1/s_aux(v)
    return sum_final

add_to_lists(beauchamp_index, efficient_invariants, all_invariants)

def subcubic_tr(g):
    """
    Returns the maximum number of vertex disjoint triangles of the graph

    Harant, Jochen, et al. "The independence number in graphs of maximum degree three." Discrete Mathematics 308.23 (2008): 5829-5833.
    """
    return len(form_triangles_graph(g).connected_components())
add_to_lists(subcubic_tr, efficient_invariants, all_invariants)

def edge_clustering_centrality(g, edge = None):
    """
    Returns edge clustering centrality for all edges in a list, or a single centrality for the given edge
    Utility to be used with min, avg, max invariants
    INPUT: g - a graph
           edge - (default: None) An edge in g. If given, will compute centrality for given edge, otherwise all edges. See Graph.has_Edge for acceptable input.
    From:
    An Application of Edge Clustering Centrality to Brain Connectivity by Joy Lind, Frank Garcea, Bradford Mahon, Roger Vargas, Darren A. Narayan

    TESTS:
        sage: edge_clustering_centrality(graphs.CompleteGraph(5))
        [5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
        sage: edge_clustering_centrality(graphs.CompleteBipartiteGraph(3,4))
        [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
        sage: edge_clustering_centrality(graphs.PetersenGraph())
        [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
        sage: edge_clustering_centrality(graphs.BullGraph())
        [3, 3, 3, 2, 2]
    """
    if edge is None:
        edge_clusering_centralities = []
        for e in g.edges(labels = False):
            edge_clusering_centralities.append(len(set(g.neighbors(e[0])) & set(g.neighbors(e[1]))) + 2) # +2 for the two vertices in e
        return edge_clusering_centralities
    else:
        return len(set(g.neighbors(edge[0])) & set(g.neighbors(edge[1]))) + 2 # +2 for the two vertices in e

def max_edge_clustering_centrality(g):
    """
        sage: max_edge_clustering_centrality(p3)
        2
        sage: max_edge_clustering_centrality(paw)
        3
    """
    return max(edge_clustering_centrality(g))
add_to_lists(max_edge_clustering_centrality, efficient_invariants, all_invariants)

def min_edge_clustering_centrality(g):
    """
        sage: min_edge_clustering_centrality(p3)
        2
        sage: min_edge_clustering_centrality(paw)
        2
    """
    return min(edge_clustering_centrality(g))
add_to_lists(min_edge_clustering_centrality, efficient_invariants, all_invariants)

def mean_edge_clustering_centrality(g):
    """
        sage: mean_edge_clustering_centrality(p3)
        2
        sage: mean_edge_clustering_centrality(paw)
        11/4
    """
    centralities = edge_clustering_centrality(g)
    return sum(centralities) / len(centralities)
add_to_lists(mean_edge_clustering_centrality, efficient_invariants, all_invariants)

def local_density(g, vertex = None):
    """
    Returns local density for all vertices as a list, or a single local density for the given vertex
    INPUT: g - a graph
           vertex - (default: None) A vertex in g. If given, it will compute local density for just that vertex, otherwise for all of them

    Pavlopoulos, Georgios A., et al. "Using graph theory to analyze biological networks." BioData mining 4.1 (2011): 10.
    """
    if vertex == None:
        densities = []
        for v in g.vertices():
            densities.append(g.subgraph(g[v] + [v]).density())
        return densities
    return g.subgraph(g[vertex] + [vertex]).density()

def min_local_density(g):
    """
        sage: min_local_density(p3)
        2/3
        sage: min_local_density(paw)
        2/3
    """
    return min(local_density(g))
add_to_lists(min_local_density, efficient_invariants, all_invariants)

def max_local_density(g):
    """
        sage: max_local_density(p3)
        1
        sage: max_local_density(paw)
        1
    """
    return max(local_density(g))
add_to_lists(max_local_density, efficient_invariants, all_invariants)

def mean_local_density(g):
    """
        sage: mean_local_density(p3)
        8/9
        sage: mean_local_density(paw)
        11/12
    """
    densities = local_density(g)
    return sum(densities) / len(densities)
add_to_lists(mean_local_density, efficient_invariants, all_invariants)

def card_simple_blocks(g):
    """
    returns the number of blocks with order 2

        sage: card_simple_blocks(k10)
        0
        sage: card_simple_blocks(paw)
        1
        sage: card_simple_blocks(kite_with_tail)
        1
    """
    blocks = g.blocks_and_cut_vertices()[0]
    count = 0
    for block in blocks:
        if len(block) == 2:
            count += 1
    return count
add_to_lists(card_simple_blocks, efficient_invariants, all_invariants)

# Block of more than 2 vertices
def card_complex_blocks(g):
    """
    returns the number of blocks with order 2

        sage: card_complex_blocks(k10)
        1
        sage: card_complex_blocks(paw)
        1
        sage: card_complex_blocks(kite_with_tail)
        1
    """
    blocks = g.blocks_and_cut_vertices()[0]
    count = 0
    for block in blocks:
        if len(block) > 2:
            count += 1
    return count
add_to_lists(card_complex_blocks, efficient_invariants, all_invariants)

# Block is a clique and more than 2 vertices
def card_complex_cliques(g):
    """
    returns the number of blocks with order 2

        sage: card_complex_cliques(k10)
        1
        sage: card_complex_cliques(paw)
        1
        sage: card_complex_cliques(kite_with_tail)
        0
    """
    blocks = g.blocks_and_cut_vertices()[0]
    count = 0
    for block in blocks:
        h = g.subgraph(block)
        if h.is_clique() and h.order() > 2:
            count += 1
    return count
add_to_lists(card_complex_cliques, efficient_invariants, all_invariants)

def max_minus_min_degrees(g):
    return max_degree(g) - min_degree(g)
add_to_lists(max_minus_min_degrees, efficient_invariants, all_invariants)

def randic_irregularity(g):
    return order(g)/2 - randic(g)
add_to_lists(randic_irregularity, efficient_invariants, all_invariants)

def degree_variance(g):
    avg_degree = g.average_degree()
    return 1/order(g) * sum([d**2 - avg_degree for d in [g.degree(v) for v in g.vertices()]])
add_to_lists(degree_variance, efficient_invariants, all_invariants)

def sum_edges_degree_difference(g):
    return sum([abs(g.degree(e[0]) - g.degree(e[1])) for e in g.edges()])
add_to_lists(sum_edges_degree_difference, efficient_invariants, all_invariants)

def one_over_size_sedd(g):
    return 1/g.size() * sum_edges_degree_difference(g)
add_to_lists(one_over_size_sedd, efficient_invariants, all_invariants)

def largest_eigenvalue_minus_avg_degree(g):
    return max_eigenvalue(g) - g.average_degree()
add_to_lists(largest_eigenvalue_minus_avg_degree, efficient_invariants, all_invariants)

def min_betweenness_centrality(g):
    centralities = g.centrality_betweenness(exact=True)
    return centralities[min(centralities)]
add_to_lists(min_betweenness_centrality, efficient_invariants, all_invariants)

def max_betweenness_centrality(g):
    centralities = g.centrality_betweenness(exact=True)
    return centralities[max(centralities)]
add_to_lists(max_betweenness_centrality, efficient_invariants, all_invariants)

def mean_betweenness_centrality(g):
    centralities = g.centrality_betweenness(exact=True)
    return sum([centralities[vertex] for vertex in g.vertices()]) / g.order()
add_to_lists(mean_betweenness_centrality, efficient_invariants, all_invariants)

def min_centrality_closeness(g):
    centralities = g.centrality_closeness()
    return centralities[min(centralities)]
add_to_lists(min_centrality_closeness, efficient_invariants, all_invariants)

def max_centrality_closeness(g):
    centralities = g.centrality_closeness()
    return centralities[max(centralities)]
add_to_lists(max_centrality_closeness, efficient_invariants, all_invariants)

def mean_centrality_closeness(g):
    centralities = g.centrality_closeness()
    return sum([centralities[vertex] for vertex in g.vertices()]) / g.order()
add_to_lists(mean_centrality_closeness, efficient_invariants, all_invariants)

def min_centrality_degree(g):
    centralities = g.centrality_degree()
    return centralities[min(centralities)]
add_to_lists(min_centrality_degree, efficient_invariants, all_invariants)

def max_centrality_degree(g):
    centralities = g.centrality_degree()
    return centralities[max(centralities)]
add_to_lists(max_centrality_degree, efficient_invariants, all_invariants)

def mean_centrality_degree(g):
    centralities = g.centrality_degree()
    return sum([centralities[vertex] for vertex in g.vertices()]) / g.order()
add_to_lists(mean_centrality_degree, efficient_invariants, all_invariants)

def homo_lumo_gap(g):
    order = g.order()
    if order % 2 != 0:
        return 0
    eigenvalues = g.spectrum()
    # Minus 1 accounts for the 0 indexing of a list
    return eigenvalues[floor((order+1)/2) - 1] - eigenvalues[ceil((order+1)/2) - 1]
add_to_lists(homo_lumo_gap, efficient_invariants, all_invariants)

def homo_lumo_index(g):
    order = g.order()
    eigenvalues = g.adjacency_matrix(sparse=False).change_ring(RDF).eigenvalues(algorithm="symmetric")
    if order%2 == 0:
        # Minus 1 accounts for the 0 indexing of a list
        return max(abs(eigenvalues[floor((order+1)/2) - 1]), abs(eigenvalues[ceil((order+1)/2) - 1]))
    else:
        return eigenvalues[floor(order/2)]
add_to_lists(homo_lumo_index, efficient_invariants, all_invariants)

def neighborhood_union_nonadjacent(g):
    # Define that for copmlete graphs (i.e. nothing to minimize over later), return n, which is trivial upper bound.
    all_dist = g.distance_all_pairs()
    nonadj = [(v,w) for v in g for w in g if all_dist[v][w] > 1]
    if not nonadj:
        return g.order()
    else:
        return min( len(union(g.neighbors(v), g.neighbors(w))) for (v,w) in nonadj)
add_to_lists(neighborhood_union_nonadjacent, efficient_invariants, all_invariants)

def neighborhood_union_dist2(g):
    # Define that for graphs with no dist 2 (i.e. nothing to minimize over later), return n, which is trivial upper bound.
    all_dist = g.distance_all_pairs()
    dist2 = [(v,w) for v in g for w in g if all_dist[v][w] == 2]
    if not dist2:
        return g.order()
    else:
        return min( len(union(g.neighbors(v), g.neighbors(w))) for (v, w) in dist2)
add_to_lists(neighborhood_union_dist2, efficient_invariants, all_invariants)

def simplical_vertices(g):
    """
    The number of simplical vertices in g.
    v is simplical if the induced nieghborhood is a clique.
    """
    return sum( is_simplical_vertex(g,v) for v in g.vertices() )
add_to_lists(simplical_vertices, efficient_invariants, all_invariants)

def first_zagreb_index(g):
    """
    The sume of squares of the degrees
    """
    return sum(g.degree(v)**2 for v in g.vertices())
add_to_lists(first_zagreb_index, efficient_invariants, all_invariants)

def degree_two_vertices(g):
    """
    The number of degree 2 vertices
    """
    return len([deg for deg in g.degree() if deg == 2])
add_to_lists(degree_two_vertices, efficient_invariants, all_invariants)

def degree_order_minus_one_vertices(g):
    """
    The number of vertices with degree = n-1
    """
    return len([deg for deg in g.degree() if deg == g.order() - 1])
add_to_lists(degree_order_minus_one_vertices, efficient_invariants, all_invariants)

def maximum_degree_vertices(g):
    """
    The number of vertices with degree equal to the maximum degree
    """
    return len([deg for deg in g.degree() if deg == max_degree(g)])
add_to_lists(maximum_degree_vertices, efficient_invariants, all_invariants)

def minimum_degree_vertices(g):
    """
    The number of vertices with degree equal to the minimum degree
    """
    return len([deg for deg in g.degree() if deg == min_degree(g)])
add_to_lists(minimum_degree_vertices, efficient_invariants, all_invariants)

def second_zagreb_index(g):
    """
    The sum over all edges (v,w) of the product of degrees(v)*degree(w)
    """
    return sum(g.degree(v)*g.degree(w) for (v,w) in g.edge_iterator(labels=False))
add_to_lists(second_zagreb_index, efficient_invariants, all_invariants)

# Damir Vukicevic, Qiuli Li, Jelena Sedlar, and Tomislav Doslic, Lanzhou Index. MATCH Commun. Math. Comput. Chem., 80: 863-876, 2018.
def lanzhou_index(g):
    """
    The sum over all vertices v of products of the co-degree of v (deg(v) in the complement of g) times the square of deg(v).

    sage: lanzhou_index(graphs.CompleteGraph(10))
    0
    sage: lanzhou_index(graphs.CompleteBipartiteGraph(5,5))
    1000
    """
    n = g.order()
    return sum( ((n-1) - g.degree(v)) * (g.degree(v) ** 2) for v in g.vertices() )
add_to_lists(lanzhou_index, efficient_invariants, all_invariants)

def friendship_number(g):
    """
    The friendship number of a graph is the number of pairs of vertices that have a unique common neighbour.

    sage: friendship_number(graphs.FriendshipGraph(3))
    21
    sage: friendship_number(graphs.CompleteGraph(7))
    0
    """
    from itertools import combinations
    return sum((1 if len(common_neighbors(g, u, v))==1 else 0) for (u,v) in combinations(g.vertices(), 2))
add_to_lists(friendship_number, efficient_invariants, all_invariants)

#####
# INTRACTABLE INVATIANTS
#####
def domination_number(g):
    """
    Returns the domination number of the graph g, i.e., the size of a maximum
    dominating set.

    A complete graph is dominated by any of its vertices::

        sage: domination_number(graphs.CompleteGraph(5))
        1

    A star graph is dominated by its central vertex::

        sage: domination_number(graphs.StarGraph(5))
        1

    The domination number of a cycle of length n is the ceil of n/3.

        sage: domination_number(graphs.CycleGraph(5))
        2
    """
    return g.dominating_set(value_only=True)
add_to_lists(domination_number, intractable_invariants, all_invariants)

def independence_number(g):
    return g.independent_set(value_only=True)
add_to_lists(independence_number, intractable_invariants, all_invariants)

def clique_covering_number(g):
    # Finding the chromatic number of the complement of a fullerene
    # is extremely slow, even when using MILP as the algorithm.
    # Therefore we check to see if the graph is triangle-free.
    # If it is, then the clique covering number is equal to the
    # number of vertices minus the size of a maximum matching.
    if g.is_triangle_free():
        return g.order() - matching_number(g)
    gc = g.complement()
    return gc.chromatic_number(algorithm="MILP")
add_to_lists(clique_covering_number, intractable_invariants, all_invariants)

def n_over_alpha(g):
    n = g.order() + 0.0
    return n/independence_number(g)
add_to_lists(n_over_alpha, intractable_invariants, all_invariants)

def independent_dominating_set_number(g):
    return g.dominating_set(value_only=True, independent=True)
add_to_lists(independent_dominating_set_number, intractable_invariants, all_invariants)

# Clearly intractable
# alpha / order
def independence_ratio(g):
    return independence_number(g)/(g.order()+0.0)
add_to_lists(independence_ratio, intractable_invariants, all_invariants)

def min_degree_of_max_ind_set(g):
    """
    Returns the minimum degree of any vertex that is a part of any maximum indepdendent set

    sage: min_degree_of_max_ind_set(c4)
    2
    sage: min_degree_of_max_ind_set(graphs.PetersenGraph())
    3
    """

    low_degree = g.order()
    list_of_vertices = []

    UnionSet = Set({})
    IndSets = find_all_max_ind_sets(g)

    for s in IndSets:
        UnionSet = UnionSet.union(Set(s))

    list_of_vertices = list(UnionSet)

    for v in list_of_vertices:
        if g.degree(v) < low_degree:
            low_degree = g.degree(v)

    return low_degree
add_to_lists(min_degree_of_max_ind_set, intractable_invariants, all_invariants)

def bipartite_number(g):
    """
    Defined as the largest number of vertices that induces a bipartite subgraph

    sage: bipartite_number(graphs.PetersenGraph())
    7
    sage: bipartite_number(c4)
    4
    sage: bipartite_number(graphs.CompleteGraph(3))
    2
    """
    if g.is_bipartite():
        return g.order()
    return len(max_bipartite_set(g, [], g.vertices()))
add_to_lists(bipartite_number, intractable_invariants, all_invariants)

# Needs Enhancement
def edge_bipartite_number(g):
    """
    Defined as the largest number of edges in an induced bipartite subgraph

        sage: edge_bipartite_number(graphs.CompleteGraph(5))
        1
        sage: edge_bipartite_number(graphs.CompleteBipartiteGraph(5, 5))
        25
        sage: edge_bipartite_number(graphs.ButterflyGraph())
        2
    """
    return g.subgraph(max_bipartite_set(g, [], g.vertices())).size()
add_to_lists(edge_bipartite_number, intractable_invariants, all_invariants)

def cheeger_constant(g):
    """
    Defined at https://en.wikipedia.org/wiki/Cheeger_constant_(graph_theory)

    sage: cheeger_constant(graphs.PathGraph(2))
    1
    sage: cheeger_constant(graphs.CompleteGraph(5))
    3
    sage: cheeger_constant(paw)
    1
    """
    n = g.order()
    upper = floor(n/2)

    v = g.vertices()
    SetV = Set(v)

    temp = g.order()
    best = n

    for i in range(1, upper+1):
        for s in SetV.subsets(i):
            count = 0
            for u in s:
                for w in SetV.difference(s):
                    for e in g.edges(labels=false):
                        if Set([u,w]) == Set(e):
                            count += 1
            temp = count/i
            if temp < best:
                best = temp
    return best
add_to_lists(cheeger_constant, intractable_invariants, all_invariants)

def tr(g):
    """
    Returns the maximum number of vertex disjoint triangles of the graph

    Harant, Jochen, et al. "The independence number in graphs of maximum degree three." Discrete Mathematics 308.23 (2008): 5829-5833.
    """
    if is_subcubic(g):
        return subcubic_tr(g)
    return independence_number(form_triangles_graph(g))
add_to_lists(tr, intractable_invariants, all_invariants)

def total_domination_number(g):
    return g.dominating_set(total=True, value_only=True)
add_to_lists(total_domination_number, intractable_invariants, all_invariants)

# A graph G is t-tough for real t if for every integer k>1, G cannot be split into k connected components by removal of fewer than tk vertices
# Returns Infinity if g is complete
# Inefficient to calculate
def toughness(g):
    """
    Tests:
        sage: toughness(graphs.PathGraph(3))
        0.5
        sage: toughness(graphs.CompleteGraph(5))
        +Infinity
        sage: toughness(graphs.PetersenGraph())
        1.3333333333333333
    """
    order = g.order()
    t = Infinity
    for x in Subsets(g.vertices()):
        if x and len(x) != order: # Proper, non-empty subset
            H = copy(g)
            H.delete_vertices(x)
            k = H.connected_components_number()
            if k > 1:
                t = min(float(len(x)) / k, t)
    return t
add_to_lists(toughness, intractable_invariants, all_invariants)

# Sigma_k = min( sum( degrees(v_i) : every k-element independent set v_1,..,v_k ) )
# Inefficient to calculate
def sigma_k(g,k):
    """
    Tests:
        sage: sigma_k(graphs.CompleteGraph(5), 1)
        4
        sage: sigma_k(graphs.PathGraph(4), 2)
        2
    """
    sigma = Infinity
    for S in Subsets(g.vertices(), k):
        if g.is_independent_set(S):
            sigma = min(sigma, sum([g.degree(x) for x in S]) )
    return sigma

def sigma_2(g):
    return sigma_k(g,2)
def sigma_3(g):
    return sigma_k(g,3)
add_to_lists(sigma_2, intractable_invariants, all_invariants)
add_to_lists(sigma_3, intractable_invariants, all_invariants)

def homogenous_number(g):
    """
    Equals the larger of the independence number or the clique number
    """
    return max(independence_number(g), g.clique_number())
add_to_lists(homogenous_number, intractable_invariants, all_invariants)

def edge_domination_number(g):
    """
    The minimum size of a set of edges S such that every edge not in S is incident to an edge in S
    """
    return domination_number(g.line_graph())
add_to_lists(edge_domination_number, intractable_invariants, all_invariants)

def circumference(g):
    """
    Returns length of longest cycle in g

    If acyclic, throws a ValueError. Some define this to be 0; we leave it up to the user.
    """
    lengths = cycle_lengths(g)
    if not lengths:
        raise ValueError("Graph is acyclic. Circumference undefined")
    else:
        return max(lengths)
add_to_lists(circumference, intractable_invariants, all_invariants)

def tree_number(g):
    """
    The order of a maximum-size induced subgraph that's a tree in g

    See Erdös, Paul, Michael Saks, and Vera T. Sós. "Maximum induced trees in graphs." Journal of Combinatorial Theory, Series B 41.1 (1986): 61-79.
    """
    return max_induced_tree(g).order()
add_to_lists(tree_number, intractable_invariants, all_invariants)

def forest_number(g):
    """
    The order of a maximum-size induced subgraph of g that's a forest
    """
    return max_induced_forest(g).order()
add_to_lists(forest_number, intractable_invariants, all_invariants)

def minimum_maximal_matching_size(g):
    """
    The minimum number of edges k s.t. there exists a matching of size k which is not extendable
    """
    if(g.size() == 0):
        return 0

    matchings_old = []
    matchings = [[e] for e in g.edges()]
    while True:
        matchings_old = matchings
        matchings = []
        for matching in matchings_old:
            extendable = False
            for e in (edge for edge in g.edges() if edge not in matching):
                possible_matching = matching + [e]
                if is_matching(possible_matching):
                    matchings.append(possible_matching)
                    extendable = True
            if not extendable:
                return len(matching)
add_to_lists(minimum_maximal_matching_size, intractable_invariants, all_invariants)

def hamiltonian_index(g):
    """
    Returns i, where L^i(g) = L(L(L(...L(g)))) is the first line graph iterate of g such that L^i(g) is Hamiltonian

    If g is Hamiltonian, then h(G) = 0.
    Raises ValueError if g is disconnected or if g is a simple path, since h(g) is undefined for either.

    Defined in: Chartrand, Gary. "On hamiltonian line-graphs." Transactions of the American Mathematical Society 134.3 (1968): 559-566.

    sage: hamiltonian_index(graphs.CycleGraph(5))
    0
    sage: hamiltonian_index(graphs.PetersenGraph())
    1
    sage: hamiltonian_index(graphs.TadpoleGraph(4, 3))
    3
    """
    if not g.is_connected():
        raise ValueError("The input graph g is not connected. The Hamiltonian index is only defined for connected graphs.")
    if g.is_isomorphic(graphs.PathGraph(g.order())):
        raise ValueError("The input graph g is a simple path. The Hamiltonian index is not defined for path graphs.")
    line_graph_i = g
    for index in xrange(0, (g.order() - 3) + 1): # [Chartrand, 68] proved index is upper bounded by n - 3.
        if line_graph_i.is_hamiltonian():
            return index
        line_graph_i = line_graph_i.line_graph()
add_to_lists(hamiltonian_index, intractable_invariants, all_invariants)


#FAST ENOUGH (tested for graphs on 140921): lovasz_theta, clique_covering_number, all efficiently_computable
#SLOW but FIXED for SpecialGraphs

print("loaded invariants")

#############################################################################
# End of invariants section                                                 #
#############################################################################
# GRAPH PROPERTIES

def has_star_center(g):
    """
    Evalutes whether graph ``g`` has a vertex adjacent to all others.

    EXAMPLES:

        sage: has_star_center(flower_with_3_petals)
        True

        sage: has_star_center(c4)
        False

    Edge cases ::

        sage: has_star_center(Graph(1))
        True

        sage: has_star_center(Graph(0))
        False
    """
    return (g.order() - 1) in g.degree()

def is_complement_of_chordal(g):
    """
    Evaluates whether graph ``g`` is a complement of a chordal graph.

    A chordal graph is one in which all cycles of four or more vertices have a
    chord, which is an edge that is not part of the cycle but connects two
    vertices of the cycle.

    EXAMPLES:

        sage: is_complement_of_chordal(p4)
        True

        sage: is_complement_of_chordal(Graph(4))
        True

        sage: is_complement_of_chordal(p5)
        False

    Any graph without a 4-or-more cycle is vacuously chordal. ::

        sage: is_complement_of_chordal(graphs.CompleteGraph(4))
        True

        sage: is_complement_of_chordal(Graph(3))
        True

        sage: is_complement_of_chordal(Graph(0))
        True
    """
    return g.complement().is_chordal()

def pairs_have_unique_common_neighbor(g):
    """
    Evalaute if each pair of vertices in ``g`` has exactly one common neighbor.

    Also known as the friendship property.
    By the Friendship Theorem, the only connected graphs with the friendship
    property are flowers.

    EXAMPLES:

        sage: pairs_have_unique_common_neighbor(flower(5))
        True

        sage: pairs_have_unique_common_neighbor(k3)
        True

        sage: pairs_have_unique_common_neighbor(k4)
        False

        sage: pairs_have_unique_common_neighbor(graphs.CompleteGraph(2))
        False

    Vacuous cases ::

        sage: pairs_have_unique_common_neighbor(Graph(1))
        True

        sage: pairs_have_unique_common_neighbor(Graph(0))
        True
    """
    from itertools import combinations
    for (u,v) in combinations(g.vertices(), 2):
        if len(common_neighbors(g, u, v)) != 1:
            return False
    return True

def is_distance_transitive(g):
    """
    Evaluates if graph ``g`` is distance transitive.

    A graph is distance transitive if all a,b,u,v satisfy that
    dist(a,b) = dist(u,v) implies there's an automorphism with a->u and b->v.

    EXAMPLES:

        sage: is_distance_transitive(graphs.CompleteGraph(4))
        True

        sage: is_distance_transitive(graphs.PetersenGraph())
        True

        sage: is_distance_transitive(Graph(3))
        True

        sage: is_distance_transitive(graphs.ShrikhandeGraph())
        False

    This method accepts disconnected graphs. ::

        sage: is_distance_transitive(graphs.CompleteGraph(3).disjoint_union(graphs.CompleteGraph(3)))
        True

        sage: is_distance_transitive(graphs.CompleteGraph(2).disjoint_union(Graph(2)))
        False

    Vacuous cases ::

        sage: is_distance_transitive(Graph(0))
        True

        sage: is_distance_transitive(Graph(1))
        True

        sage: is_distance_transitive(Graph(2))
        True

    ... WARNING ::

        This method calls, via the automorphism group, the Gap package. This
        package behaves badly with most threading or multiprocessing tools.
    """
    from itertools import combinations
    dist_dict = g.distance_all_pairs()
    auto_group = g.automorphism_group()

    for d in g.distances_distribution():
        sameDistPairs = []
        for (u,v) in combinations(g.vertices(), 2):
            # By default, no entry if disconnected. We substitute +Infinity.
            if dist_dict[u].get(v, +Infinity) == d:
                sameDistPairs.append(Set([u,v]))
        if len(sameDistPairs) >= 2:
            if len(sameDistPairs) != len(auto_group.orbit(sameDistPairs[0], action = "OnSets")):
                return False
    return True

def is_dirac(g):
    """
    Evaluates if graph ``g`` has order at least 3 and min. degree at least n/2.

    See Dirac's Theorem: If graph is_dirac, then it is hamiltonian.

    EXAMPLES:

        sage: is_dirac(graphs.CompleteGraph(6))
        True

        sage: is_dirac(graphs.CompleteGraph(3))
        True

        sage: is_dirac(graphs.CompleteGraph(2))
        False

        sage: is_dirac(graphs.CycleGraph(5))
        False
    """
    n = g.order()
    return n > 2 and min(g.degree()) >= n/2

def is_ore(g):
    """
    Evaluate if deg(v)+deg(w)>=n for all non-adjacent pairs v,w in graph ``g``.

    See Ore's Theorem: If graph is_ore, then it is hamiltonian.

    EXAMPLES:

        sage: is_ore(graphs.CompleteGraph(5))
        True

        sage: is_ore(graphs.CompleteGraph(2))
        True

        sage: is_ore(dart)
        False

        sage: is_ore(Graph(2))
        False

        sage: is_ore(graphs.CompleteGraph(2).disjoint_union(Graph(1)))
        False

    Vacous cases ::

        sage: is_ore(Graph(0))
        True

        sage: is_ore(Graph(1))
        True
    """
    A = g.adjacency_matrix()
    n = g.order()
    D = g.degree()
    for i in xrange(n):
        for j in xrange(i):
            if A[i][j]==0:
                if D[i] + D[j] < n:
                    return False
    return True

def is_haggkvist_nicoghossian(g):
    """
    Evaluates if g is 2-connected and min degree >= (n + vertex_connectivity)/3.

    INPUT:

    - ``g`` -- graph

    EXAMPLES:

        sage: is_haggkvist_nicoghossian(graphs.CompleteGraph(3))
        True

        sage: is_haggkvist_nicoghossian(graphs.CompleteGraph(5))
        True

        sage: is_haggkvist_nicoghossian(graphs.CycleGraph(5))
        False

        sage: is_haggkvist_nicoghossian(graphs.CompleteBipartiteGraph(4,3)
        False

        sage: is_haggkvist_nicoghossian(Graph(1))
        False

        sage: is_haggkvist_nicoghossian(graphs.CompleteGraph(2))
        False

    REFERENCES:

    Theorem: If a graph ``is_haggkvist_nicoghossian``, then it is Hamiltonian.

    .. [HN1981]     \R. Häggkvist and G. Nicoghossian, "A remark on Hamiltonian
                    cycles". Journal of Combinatorial Theory, Series B, 30(1):
                    118--120, 1981.
    """
    k = g.vertex_connectivity()
    return k >= 2 and min(g.degree()) >= (1.0/3) * (g.order() + k)

def is_genghua_fan(g):
    """
    Evaluates if graph ``g`` satisfies a condition for Hamiltonicity by G. Fan.

    OUTPUT:

    Returns ``True`` if ``g`` is 2-connected and satisfies that
    `dist(u,v)=2` implies `\max(deg(u), deg(v)) \geq n/2` for all
    vertices `u,v`.
    Returns ``False`` otherwise.

    EXAMPLES:

        sage: is_genghua_fan(graphs.DiamondGraph())
        True

        sage: is_genghua_fan(graphs.CycleGraph(4))
        False

        sage: is_genghua_fan(graphs.ButterflyGraph())
        False

        sage: is_genghua_fan(Graph(1))
        False

    REFERENCES:

    Theorem: If a graph ``is_genghua_fan``, then it is Hamiltonian.

    .. [Fan1984]    Geng-Hua Fan, "New sufficient conditions for cycles in
                    graphs". Journal of Combinatorial Theory, Series B, 37(3):
                    221--227, 1984.
    """
    if not is_two_connected(g):
        return False
    D = g.degree()
    Dist = g.distance_all_pairs()
    V = g.vertices()
    n = g.order()
    for i in xrange(n):
        for j in xrange(i):
            if Dist[V[i]][V[j]] == 2 and max(D[i], D[j]) < n / 2.0:
                return False
    return True

def is_planar_transitive(g):
    """
    Evaluates whether graph ``g`` is planar and is vertex-transitive.

    EXAMPLES:

        sage: is_planar_transitive(graphs.HexahedralGraph())
        True

        sage: is_planar_transitive(graphs.CompleteGraph(2))
        True

        sage: is_planar_transitive(graphs.FranklinGraph())
        False

        sage: is_planar_transitive(graphs.BullGraph())
        False

    Vacuous cases ::

        sage: is_planar_transitive(Graph(1))
        True

    Sage defines `Graph(0).is_vertex_transitive() == False``. ::

        sage: is_planar_transitive(Graph(0))
        False
    """
    return g.is_planar() and g.is_vertex_transitive()

def is_generalized_dirac(g):
    """
    Test if ``graph`` g meets condition in a generalization of Dirac's Theorem.

    OUTPUT:

    Returns ``True`` if g is 2-connected and for all non-adjacent u,v,
    the cardinality of the union of neighborhood(u) and neighborhood(v)
    is `>= (2n-1)/3`.

    EXAMPLES:

        sage: is_generalized_dirac(graphs.HouseGraph())
        True

        sage: is_generalized_dirac(graphs.PathGraph(5))
        False

        sage: is_generalized_dirac(graphs.DiamondGraph())
        False

        sage: is_generalized_dirac(Graph(1))
        False

    REFERENCES:

    Theorem: If graph g is_generalized_dirac, then it is Hamiltonian.

    .. [FGJS1989]   \R.J. Faudree, Ronald Gould, Michael Jacobson, and
                    R.H. Schelp, "Neighborhood unions and hamiltonian
                    properties in graphs". Journal of Combinatorial
                    Theory, Series B, 47(1): 1--9, 1989.
    """
    from itertools import combinations

    if not is_two_connected(g):
        return False
    for (u,v) in combinations(g.vertices(), 2):
        if not g.has_edge(u,v):
            if len(neighbors_set(u, v)) < (2.0 * g.order() - 1) / 3:
                return False
    return True

def is_van_den_heuvel(g):
    """
    Evaluates if g meets an eigenvalue condition related to Hamiltonicity.

    INPUT:

    - ``g`` -- graph

    OUTPUT:

    Let ``g`` be of order `n`.
    Let `A_H` denote the adjacency matrix of a graph `H`, and `D_H` denote
    the matrix with the degrees of the vertices of `H` on the diagonal.
    Define `Q_H = D_H + A_H` and `L_H = D_H - A_H` (i.e. the Laplacian).
    Finally, let `C` be the cycle graph on `n` vertices.

    Returns ``True`` if the `i`-th eigenvalue of `L_C` is at most the `i`-th
    eigenvalue of `L_g` and the `i`-th eigenvalue of `Q_C` is at most the
    `i`-th eigenvalue of `Q_g for all `i`.

    EXAMPLES:

        sage: is_van_den_heuvel(graphs.CycleGraph(5))
        True

        sage: is_van_den_heuvel(graphs.PetersenGraph())
        False

    REFERENCES:

    Theorem: If a graph is Hamiltonian, then it ``is_van_den_heuvel``.

    .. [Heu1995]    \J.van den Heuvel, "Hamilton cycles and eigenvalues of
                    graphs". Linear Algebra and its Applications, 226--228:
                    723--730, 1995.

    TESTS::

        sage: is_van_den_heuvel(Graph(0))
        False

        sage: is_van_den_heuvel(Graph(1))
        True
    """
    cycle_n = graphs.CycleGraph(g.order())

    cycle_laplac_eigen = sorted(cycle_n.laplacian_matrix().eigenvalues())
    g_laplac_eigen = sorted(g.laplacian_matrix().eigenvalues())
    for cycle_lambda_i, g_lambda_i in zip(cycle_laplac_eigen, g_laplac_eigen):
        if cycle_lambda_i > g_lambda_i:
            return False

    def Q(g):
        A = g.adjacency_matrix(sparse=False)
        D = matrix(g.order(), sparse=False)
        row_sums = [sum(r) for r in A.rows()]
        for i in xrange(A.nrows()):
            D[i,i] = row_sums[i]
        return D + A
    cycle_q_matrix = sorted(Q(cycle_n).eigenvalues())
    g_q_matrix = sorted(Q(g).eigenvalues())
    for cycle_q_lambda_i, g_q_lambda_i in zip(cycle_q_matrix, g_q_matrix):
        if cycle_q_lambda_i > g_q_lambda_i:
            return False

    return True

def is_two_connected(g):
    """
    Evaluates whether graph ``g`` is 2-connected.

    A 2-connected graph is a connected graph on at least 3 vertices such that
    the removal of any single vertex still gives a connected graph.
    Follows convention that complete graph `K_n` is `n-1`-connected.

    Almost equivalent to ``Graph.is_biconnected()``. We prefer our name. AND,
    while that method defines that ``graphs.CompleteGraph(2)`` is biconnected,
    we follow the convention that `K_n` is `n-1`-connected, so `K_2` is
    only 1-connected.

    EXAMPLES:

        sage: is_two_connected(graphs.CycleGraph(5))
        True

        sage: is_two_connected(graphs.CompleteGraph(3))
        True

        sage: is_two_connected(graphs.PathGraph(5))
        False

        sage: is_two_connected(graphs.CompleteGraph(2))
        False

        sage: is_two_connected(Graph(3))
        False

    Edge cases ::

        sage: is_two_connected(Graph(0))
        False

        sage: is_two_connected(Graph(1))
        False
    """
    if g.is_isomorphic(graphs.CompleteGraph(2)):
        return False
    return g.is_biconnected()

def is_three_connected(g):
    """
    Evaluates whether graph ``g`` is 3-connected.

    A 3-connected graph is a connected graph on at least 4 vertices such that
    the removal of any two vertices still gives a connected graph.
    Follows convention that complete graph `K_n` is `n-1`-connected.

    EXAMPLES:

        sage: is_three_connected(graphs.PetersenGraph())
        True

        sage: is_three_connected(graphs.CompleteGraph(4))
        True

        sage: is_three_connected(graphs.CycleGraph(5))
        False

        sage: is_three_connected(graphs.PathGraph(5))
        False

        sage: is_three_connected(graphs.CompleteGraph(3))
        False

        sage: is_three_connected(graphs.CompleteGraph(2))
        False

        sage: is_three_connected(Graph(4))
        False

    Edge cases ::

        sage: is_three_connected(Graph(0))
        False

        sage: is_three_connected(Graph(1))
        False

    .. WARNING::

        Implementation requires Sage 8.2+.
    """
    return g.vertex_connectivity(k = 3)

def is_four_connected(g):
    """
    Evaluates whether ``g`` is 4-connected.

    A 4-connected graph is a connected graph on at least 5 vertices such that
    the removal of any three vertices still gives a connected graph.
    Follows convention that complete graph `K_n` is `n-1`-connected.

    EXAMPLES:


        sage: is_four_connected(graphs.CompleteGraph(5))
        True

        sage: is_four_connected(graphs.PathGraph(5))
        False

        sage: is_four_connected(Graph(5))
        False

        sage: is_four_connected(graphs.CompleteGraph(4))
        False

    Edge cases ::

        sage: is_four_connected(Graph(0))
        False

        sage: is_four_connected(Graph(1))
        False

    .. WARNING::

        Implementation requires Sage 8.2+.
    """
    return g.vertex_connectivity(k = 4)

def is_lindquester(g):
    """
    Test if graph ``g`` meets a neighborhood union condition for Hamiltonicity.

    OUTPUT:

    Let ``g`` be of order `n`.

    Returns ``True`` if ``g`` is 2-connected and for all vertices `u,v`,
    `dist(u,v) = 2` implies that the cardinality of the union of
    neighborhood(`u`) and neighborhood(`v`) is `\geq (2n-1)/3`.
    Returns ``False`` otherwise.

    EXAMPLES:

        sage: is_lindquester(graphs.HouseGraph())
        True

        sage: is_lindquester(graphs.OctahedralGraph())
        True

        sage: is_lindquester(graphs.PathGraph(3))
        False

        sage: is_lindquester(graphs.DiamondGraph())
        False

    REFERENCES:

    Theorem: If a graph ``is_lindquester``, then it is Hamiltonian.

    .. [Lin1989]    \T.E. Lindquester, "The effects of distance and
                    neighborhood union conditions on hamiltonian properties
                    in graphs". Journal of Graph Theory, 13(3): 335-352,
                    1989.
    """
    if not is_two_connected(g):
        return False
    D = g.distance_all_pairs()
    n = g.order()
    V = g.vertices()
    for i in range(n):
        for j in range(i):
            if D[V[i]][V[j]] == 2:
                if len(neighbors_set(g,[V[i],V[j]])) < (2*n-1)/3.0:
                    return False
    return True

def is_complete(g):
    """
    Tests whether ``g`` is a complete graph.

    OUTPUT:

    Returns ``True`` if ``g`` is a complete graph; returns ``False`` otherwise.
    A complete graph is one where every vertex is connected to every others
    vertex.

    EXAMPLES:

        sage: is_complete(graphs.CompleteGraph(1))
        True

        sage: is_complete(graphs.CycleGraph(3))
        True

        sage: is_complete(graphs.CompleteGraph(6))
        True

        sage: is_complete(Graph(0))
        True

        sage: is_complete(graphs.PathGraph(5))
        False

        sage: is_complete(graphs.CycleGraph(4))
        False
    """
    n = g.order()
    e = g.size()
    if not g.has_multiple_edges():
        return e == n*(n-1)/2
    else:
        D = g.distance_all_pairs()
        for i in range(n):
            for j in range(i):
                if D[V[i]][V[j]] != 1:
                    return False
    return True

def has_c4(g):
    """
    Tests whether graph ``g`` contains Cycle_4 as an *induced* subgraph.

    EXAMPLES:

        sage: has_c4(graphs.CycleGraph(4))
        True

        sage: has_c4(graphs.HouseGraph())
        True

        sage: has_c4(graphs.CycleGraph(5))
        False

        sage: has_c4(graphs.DiamondGraph())
        False
    """
    return g.subgraph_search(c4, induced=True) is not None

def is_c4_free(g):
    """
    Tests whether graph ``g`` does not contain Cycle_4 as an *induced* subgraph.

    EXAMPLES:

        sage: is_c4_free(graphs.CycleGraph(4))
        False

        sage: is_c4_free(graphs.HouseGraph())
        False

        sage: is_c4_free(graphs.CycleGraph(5))
        True

        sage: is_c4_free(graphs.DiamondGraph())
        True
    """
    return not has_c4(g)

def has_paw(g):
    """
    Tests whether graph ``g`` contains a Paw as an *induced* subgraph.

    OUTPUT:

    Define a Paw to be a 4-vertex graph formed by a triangle and a pendant.
    Returns ``True`` if ``g`` contains a Paw as an induced subgraph.
    Returns ``False`` otherwise.

    EXAMPLES:

        sage: has_paw(paw)
        True

        sage: has_paw(graphs.BullGraph())
        True

        sage: has_paw(graphs.ClawGraph())
        False

        sage: has_paw(graphs.DiamondGraph())
        False
    """
    return g.subgraph_search(paw, induced=True) is not None

def is_paw_free(g):
    """
    Tests whether graph ``g`` does not contain a Paw as an *induced* subgraph.

    OUTPUT:

    Define a Paw to be a 4-vertex graph formed by a triangle and a pendant.
    Returns ``False`` if ``g`` contains a Paw as an induced subgraph.
    Returns ``True`` otherwise.

    EXAMPLES:

        sage: is_paw_free(paw)
        False

        sage: is_paw_free(graphs.BullGraph())
        False

        sage: is_paw_free(graphs.ClawGraph())
        True

        sage: is_paw_free(graphs.DiamondGraph())
        True
    """
    return not has_paw(g)

def has_dart(g):
    """
    Tests whether graph ``g`` contains a Dart as an *induced* subgraph.

    OUTPUT:

    Define a Dart to be a 5-vertex graph formed by ``graphs.DiamondGraph()``
    with and a pendant added to one of the degree-3 vertices.
    Returns ``True`` if ``g`` contains a Dart as an induced subgraph.
    Returns ``False`` otherwise.

    EXAMPLES:

        sage: has_dart(dart)
        True

        sage: has_dart(umbrella_4)
        True

        sage: has_dart(graphs.DiamondGraph())
        False

        sage: has_dart(bridge)
        False
    """
    return g.subgraph_search(dart, induced=True) is not None

def is_dart_free(g):
    """
    Tests whether graph ``g`` does not contain a Dart as an *induced* subgraph.

    OUTPUT:

    Define a Dart to be a 5-vertex graph formed by ``graphs.DiamondGraph()``
    with and a pendant added to one of the degree-3 vertices.
    Returns ``False`` if ``g`` contains a Dart as an induced subgraph.
    Returns ``True`` otherwise.

    EXAMPLES:

        sage: is_dart_free(dart)
        False

        sage: is_dart_free(umbrella_4)
        False

        sage: is_dart_free(graphs.DiamondGraph())
        True

        sage: is_dart_free(bridge)
        True
    """
    return not has_dart(g)

def is_p4_free(g):
    """
    Equivalent to is a cograph - https://en.wikipedia.org/wiki/Cograph
    """
    return not has_p4(g)

def has_p4(g):
    """
    Tests whether graph ``g`` contains a Path_4 as an *induced* subgraph.

    Might also be known as "is not a cograph".

    EXAMPLES:

        sage: has_p4(graphs.PathGraph(4))
        True

        sage: has_p4(graphs.CycleGraph(5))
        True

        sage: has_p4(graphs.CycleGraph(4))
        False

        sage: has_p4(graphs.CompleteGraph(5))
        False
    """
    return g.subgraph_search(p4, induced=True) is not None

def has_kite(g):
    """
    Tests whether graph ``g`` contains a Kite as an *induced* subgraph.

    A Kite is a 5-vertex graph formed by a ``graphs.DiamondGraph()`` with a
    pendant attached to one of the degree-2 vertices.

    EXAMPLES:

        sage: has_kite(kite_with_tail)
        True

        sage: has_kite(graphs.KrackhardtKiteGraph())
        True

        sage: has_kite(graphs.DiamondGraph())
        False

        sage: has_kite(bridge)
        False
    """
    return g.subgraph_search(kite_with_tail, induced=True) is not None

def is_kite_free(g):
    """
    Tests whether graph ``g`` does not contain a Kite as an *induced* subgraph.

    A Kite is a 5-vertex graph formed by a ``graphs.DiamondGraph()`` with a
    pendant attached to one of the degree-2 vertices.

    EXAMPLES:

        sage: is_kite_free(kite_with_tail)
        False

        sage: is_kite_free(graphs.KrackhardtKiteGraph())
        False

        sage: is_kite_free(graphs.DiamondGraph())
        True

        sage: is_kite_free(bridge)
        True
    """
    return not has_kite(g)

def has_claw(g):
    """
    Tests whether graph ``g`` contains a Claw as an *induced* subgraph.

    A Claw is a 4-vertex graph with one central vertex and 3 pendants.
    This is encoded as ``graphs.ClawGraph()``.

    EXAMPLES:

        sage: has_claw(graphs.ClawGraph())
        True

        sage: has_claw(graphs.PetersenGraph())
        True

        sage: has_claw(graphs.BullGraph())
        False

        sage: has_claw(graphs.HouseGraph())
        False
    """
    return g.subgraph_search(graphs.ClawGraph(), induced=True) is not None

def is_claw_free(g):
    """
    Tests whether graph ``g`` does not contain a Claw as an *induced* subgraph.

    A Claw is a 4-vertex graph with one central vertex and 3 pendants.
    This is encoded as ``graphs.ClawGraph()``.

    EXAMPLES:

        sage: is_claw_free(graphs.ClawGraph())
        False

        sage: is_claw_free(graphs.PetersenGraph())
        False

        sage: is_claw_free(graphs.BullGraph())
        True

        sage: is_claw_free(graphs.HouseGraph())
        True
    """
    return not has_claw(g)

def has_H(g):
    """
    Tests whether graph ``g`` contains an H graph as an *induced* subgraph.

    An H graph may also be known as a double fork. It is a 6-vertex graph
    formed by two Path_3s with their midpoints joined by a bridge.

    EXAMPLES:

        sage: has_H(double_fork)
        True

        sage: has_H(graphs.PetersenGraph())
        True

        sage: has_H(ce71) # double_fork with extra edge
        False

        sage: has_H(graphs.BullGraph())
        False
    """
    return g.subgraph_search(double_fork, induced=True) is not None

def is_H_free(g):
    """
    Tests if graph ``g`` does not contain a H graph as an *induced* subgraph.

    An H graph may also be known as a double fork. It is a 6-vertex graph
    formed by two Path_3s with their midpoints joined by a bridge.

    EXAMPLES:

        sage: is_H_free(double_fork)
        False

        sage: is_H_free(graphs.PetersenGraph())
        False

        sage: is_H_free(ce71) # double_fork with extra edge
        True

        sage: is_H_free(graphs.BullGraph())
        True
    """
    return not has_H(g)

def has_fork(g):
    """
    Tests if graph ``g`` contains a Fork graph as an *induced* subgraph.

    A Fork graph may also be known as a Star_1_1_3. It is a 6-vertex graph
    formed by a Path_4 with two pendants connected to one end.
    It is stored as `star_1_1_3`.

    EXAMPLES:

        sage: has_fork(star_1_1_3)
        True

        sage: has_fork(graphs.PetersenGraph())
        True

        sage: has_fork(graphs.LollipopGraph(3, 2))
        False

        sage: has_fork(graphs.HouseGraph())
        False

        sage: has_fork(graphs.ClawGraph())
        False
    """
    return g.subgraph_search(star_1_1_3, induced=True) is not None

def is_fork_free(g):
    """
    Tests if graph ``g`` does not contain Fork graph as an *induced* subgraph.

    A Fork graph may also be known as a Star_1_1_3. It is a 6-vertex graph
    formed by a Path_4 with two pendants connected to one end.
    It is stored as `star_1_1_3`.

    EXAMPLES:

        sage: is_fork_free(star_1_1_3)
        False

        sage: is_fork_free(graphs.PetersenGraph())
        False

        sage: is_fork_free(graphs.LollipopGraph(3, 2))
        True

        sage: is_fork_free(graphs.HouseGraph())
        True

        sage: is_fork_free(graphs.ClawGraph())
        True
    """
    return not has_fork(g)

def has_k4(g):
    """
    Tests if graph ``g`` contains a `K_4` as an *induced* subgraph.

    `K_4` is the complete graph on 4 vertices.

    EXAMPLES:

        sage: has_k4(graphs.CompleteGraph(4))
        True

        sage: has_k4(graphs.CompleteGraph(5))
        True

        sage: has_k4(graphs.CompleteGraph(3))
        False

        sage: has_k4(graphs.PetersenGraph())
        False
    """
    return g.subgraph_search(alpha_critical_easy[2], induced=True) is not None

def is_k4_free(g):
    """
    Tests if graph ``g`` does not contain a `K_4` as an *induced* subgraph.

    `K_4` is the complete graph on 4 vertices.

    EXAMPLES:

        sage: is_k4_free(graphs.CompleteGraph(4))
        False

        sage: is_k4_free(graphs.CompleteGraph(5))
        False

        sage: is_k4_free(graphs.CompleteGraph(3))
        True

        sage: is_k4_free(graphs.PetersenGraph())
        True
    """
    return not has_k4(g)

def is_double_clique(g):
    """
    Tests if graph ``g`` can be partitioned into 2 sets which induce cliques.

    EXAMPLE:

        sage: is_double_clique(p4)
        True

        sage: is_double_clique(graphs.ButterflyGraph())
        True

        sage: is_double_clique(graphs.CompleteBipartiteGraph(3,4))
        False

        sage: is_double_clique(graphs.ClawGraph())
        False

        sage: is_double_clique(Graph(3))
        False

    Edge cases ::

        sage: is_double_clique(Graph(0))
        True

        sage: is_double_clique(Graph(1))
        True

        sage: is_double_clique(Graph(2))
        True
    """
    gc = g.complement()
    return gc.is_bipartite()

def has_radius_equal_diameter(g):
    """
    Evaluates whether the radius of graph ``g`` equals its diameter.

    Recall the radius of a graph is the minimum eccentricity over all vertices,
    or the minimum over all longest distances from a vertex to any other vertex.
    Diameter is the maximum eccentricity over all vertices.
    Both radius and diamter are defined to be `+Infinity` for disconnected
    graphs.

    Both radius and diameter are undefined for the empty graph.

    EXAMPLES:

        sage: has_radius_equal_diameter(Graph(4))
        True

        sage: has_radius_equal_diameter(graphs.HouseGraph())
        True

        sage: has_radius_equal_diameter(Graph(1))
        True

        sage: has_radius_equal_diameter(graphs.ClawGraph())
        False

        sage: has_radius_equal_diameter(graphs.BullGraph())
        False
    """
    return g.radius() == g.diameter()

def has_residue_equals_alpha(g):
    """
    Evaluate whether the residue of graph ``g`` equals its independence number.

    The independence number is the cardinality of the largest independent set
    of vertices in ``g``.
    The residue of a graph ``g`` with degrees `d_1 \geq d_2 \geq ... \geq d_n`
    is found iteratively. First, remove `d_1` from consideration and subtract
    `d_1` from the following `d_1` number of elements. Sort. Repeat this
    process for `d_2,d_3, ...` until only 0s remain. The number of elements,
    i.e. the number of 0s, is the residue of ``g``.

    Residue is undefined on the empty graph.

    EXAMPLES:

        sage: has_residue_equals_alpha(graphs.HouseGraph())
        True

        sage: has_residue_equals_alpha(graphs.ClawGraph())
        True

        sage: has_residue_equals_alpha(graphs.CompleteGraph(4))
        True

        sage: has_residue_equals_alpha(Graph(1))
        True

        sage: has_residue_equals_alpha(graphs.PetersenGraph())
        False

        sage: has_residue_equals_alpha(graphs.PathGraph(5))
        False
    """
    return residue(g) == independence_number(g)

def is_not_forest(g):
    """
    Evaluates if graph ``g`` is not a forest.

    A forest is a disjoint union of trees. Equivalently, a forest is any acylic
    graph, which may or may not be connected.

    EXAMPLES:
        sage: is_not_forest(graphs.BalancedTree(2,3))
        False

        sage: is_not_forest(graphs.BalancedTree(2,3).disjoint_union(graphs.BalancedTree(3,3)))
        False

        sage: is_not_forest(graphs.CycleGraph(5))
        True

        sage: is_not_forest(graphs.HouseGraph())
        True

    Edge cases ::

        sage: is_not_forest(Graph(1))
        False

        sage: is_not_forest(Graph(0))
        False
    """
    return not g.is_forest()

def has_empty_KE_part(g):
    """
    Evaluates whether graph ``g`` has an empty Konig-Egervary subgraph.

    A Konig-Egervary graph satisfies
        independence number + matching number = order.
    By [Lar2011]_, every graph contains a unique induced subgraph which is a
    Konig-Egervary graph.

    EXAMPLES:

        sage: has_empty_KE_part(graphs.PetersenGraph())
        True

        sage: has_empty_KE_part(graphs.CycleGraph(5))
        True

        sage: has_empty_KE_part(graphs.CompleteBipartiteGraph(3,4))
        False

        sage: has_empty_KE_part(graphs.CycleGraph(6))
        False

    Edge cases ::

        sage: has_empty_KE_part(Graph(1))
        False

        sage: has_empty_KE_part(Graph(0))
        True

    ALGORITHM:

    This function is implemented using the Maximum Critical Independent
    Set (MCIS) algorithm of [DL2013]_ and applying a Theorem of [Lar2011]_.

    Define that an independent set `I` is a critical independent set if
    `|I|−|N(I)| \geq |J|−|N(J)|` for any independent set J. Define that a
    maximum critical independent set is a critical independent set of maximum
    cardinality.

    By a Theorem of [Lar2011]_, for every maximum critical independent set `J`
    of `G`, the unique Konig-Egervary inducing set `X` is `X = J \cup N(J)`,
    where `N(J)` is the neighborhood of `J`.
    Therefore, the ``g`` has an empty Konig-Egervary induced subgraph if and
    only if the MCIS `J = \emptyset`.

    Next, we describe the MCIS algorithm.
    Let `B(G) = K_2 \ times G`, i.e. `B(G)` is the bipartite double cover
    of `G`. Let `v' \in B(G)` denote the new "twin" of vertex `v \in G`.
    Let `a` be the independence number of `B(G)`.
    For each vertex `v` in `B(G)`, calculate
        `t := independence number(B(G) - \{v,v'\} - N(\{v,v'\})) + 2`.
    If `t = a`, then `v` is in the MCIS.
        Since we only care about whether the MCIS is empty, if `t = a`,
        we return ``False`` and terminate.

    Finally, use the Gallai identities to show matching

    Finally, we apply the Konig-Egervary Theorem (1931) that for all bipartite
    graphs, matching number = vertex cover number. We substitute this into
    one of the Gallai identities, that
        independence number + covering number = order,
    yielding,
        independence number = order - matching number.
    Since matching number is efficient to compute, our final algorithm is
    in fact efficient.

    REFERENCES:

    .. [DL2013]     \Ermelinda DeLaVina and Craig Larson, "A parallel ALGORITHM
                    for computing the critical independence number and related
                    sets". ARS Mathematica Contemporanea 6: 237--245, 2013.

    .. [Lar2011]    \C.E. Larson, "Critical Independent Sets and an
                    Independence Decomposition Theorem". European Journal of
                    Combinatorics 32: 294--300, 2011.
    """
    b = bipartite_double_cover(g)
    alpha = b.order() - b.matching(value_only=True)
    for v in g.vertices():
        test = b.copy()
        test.delete_vertices(closed_neighborhood(b,[(v,0), (v,1)]))
        alpha_test = test.order() - test.matching(value_only=True) + 2
        if alpha_test == alpha:
            return False
    return True

def is_class1(g):
    """
    Evaluates whether the chomatic index of graph ``g`` equals its max degree.

    Let `D` be the maximum degree. By Vizing's Thoerem, all graphs can be
    edge-colored in either `D` or `D+1` colors. The case of `D` colors is
    called "class 1".

    Max degree is undefined for the empty graph.

    EXAMPLES:

        sage: is_class1(graphs.CompleteGraph(4))
        True

        sage: is_class1(graphs.WindmillGraph(4,3))
        True

        sage: is_class1(Graph(1))
        True

        sage: is_class1(graphs.CompleteGraph(3))
        False

        sage: is_class1(graphs.PetersenGraph())
        False
    """
    return g.chromatic_index() == max(g.degree())

def is_class2(g):
    """
    Evaluates whether the chomatic index of graph ``g`` equals max degree + 1.

    Let `D` be the maximum degree. By Vizing's Thoerem, all graphs can be
    edge-colored in either `D` or `D+1` colors. The case of `D+1` colors is
    called "class 2".

    Max degree is undefined for the empty graph.

    EXAMPLES:

        sage: is_class2(graphs.CompleteGraph(4))
        False

        sage: is_class2(graphs.WindmillGraph(4,3))
        False

        sage: is_class2(Graph(1))
        False

        sage: is_class2(graphs.CompleteGraph(3))
        True

        sage: is_class2(graphs.PetersenGraph())
        True
    """
    return not(g.chromatic_index() == max(g.degree()))

def is_cubic(g):
    """
    Evalutes whether graph ``g`` is cubic, i.e. is 3-regular.

    EXAMPLES:

        sage: is_cubic(graphs.CompleteGraph(4))
        True

        sage: is_cubic(graphs.PetersenGraph())
        True

        sage: is_cubic(graphs.CompleteGraph(3))
        False

        sage: is_cubic(graphs.HouseGraph())
        False
    """
    D = g.degree()
    return min(D) == 3 and max(D) == 3

def is_anti_tutte(g):
    """
    Evalutes if graph ``g`` is connected and indep. number <= diameter + girth.

    This property is satisfied by many Hamiltonian graphs, but notably not by
    the Tutte graph ``graphs.TutteGraph()``.

    Diameter is undefined for the empty graph.

    EXAMPLES:

        sage: is_anti_tutte(graphs.CompleteBipartiteGraph(4, 5))
        True

        sage: is_anti_tutte(graphs.PetersenGraph())
        True

        sage: is_anti_tutte(Graph(1))

        sage: is_anti_tutte(graphs.TutteGraph())
        False

        sage: is_anti_tutte(graphs.TutteCoxeterGraph())
        False
    """
    if not g.is_connected():
        return False
    return independence_number(g) <= g.diameter() + g.girth()

def is_anti_tutte2(g):
    """
    Tests if graph ``g`` has indep. number <= domination number + radius - 1.

    ``g`` must also be connected.
    This property is satisfied by many Hamiltonian graphs, but notably not by
    the Tutte graph ``graphs.TutteGraph()``.

    Radius is undefined for the empty graph.

    EXAMPLES:

        sage: is_anti_tutte2(graphs.CompleteGraph(5))
        True

        sage: is_anti_tutte2(graphs.PetersenGraph())
        True

        sage: is_anti_tutte2(graphs.TutteGraph())
        False

        sage: is_anti_tutte2(graphs.TutteCoxeterGraph())
        False

        sage: is_anti_tutte2(Graph(1))
        False
    """
    if not g.is_connected():
        return False
    return independence_number(g) <=  domination_number(g) + g.radius()- 1

def diameter_equals_twice_radius(g):
    """
    Evaluates whether the diameter of graph ``g`` is equal to twice its radius.

    Diameter and radius are undefined for the empty graph.

    EXAMPLES:

        sage: has_radius_equal_diameter(graphs.ClawGraph())
        True

        sage: has_radius_equal_diameter(graphs.KrackhardtKiteGraph())
        True

        sage: diameter_equals_twice_radius(graphs.HouseGraph())
        False

        sage: has_radius_equal_diameter(graphs.BullGraph())
        False

    The radius and diameter of ``Graph(1)`` are both 1. ::

        sage: diameter_equals_twice_radius(Graph(1))
        True

    Disconnected graphs have both diameter and radius equal infinity.

        sage: diameter_equals_twice_radius(Graph(4))
        True
    """
    return g.diameter() == 2*g.radius()

def diameter_equals_two(g):
    """
    Evaluates whether the diameter of graph ``g`` equals 2.

    Diameter is undefined for the empty graph.

    EXAMPLES:

        sage: diameter_equals_two(graphs.ClawGraph())
        True

        sage: diameter_equals_two(graphs.HouseGraph())
        True

        sage: diameter_equals_two(graphs.KrackhardtKiteGraph())
        False

        sage: diameter_equals_two(graphs.BullGraph())
        False

    Disconnected graphs have diameter equals infinity.

        sage: diameter_equals_two(Graph(4))
        False
    """
    return g.diameter() == 2

def has_lovasz_theta_equals_alpha(g):
    """
    Tests if the Lovasz number of graph ``g`` equals its independence number.

    Examples:

        sage: has_lovasz_theta_equals_alpha(graphs.CompleteGraph(12))
        True

        sage: has_lovasz_theta_equals_alpha(double_fork)
        True

        sage: has_lovasz_theta_equals_alpha(graphs.PetersenGraph())
        True

        sage: has_lovasz_theta_equals_alpha(graphs.ClebschGraph())
        False

        sage: has_lovasz_theta_equals_alpha(graphs.CycleGraph(24))
        False

    True for all graphs with no edges ::

        sage: has_lovasz_theta_equals_alpha(Graph(12))
        True

    Edge cases ::

        sage: has_lovasz_theta_equals_alpha(Graph(0))
        True

        # Broken. Issue #584
        sage: has_lovasz_theta_equals_alpha(Graph(1)) # doctest: +SKIP
        True
    """
    return g.lovasz_theta() == independence_number(g)

def has_lovasz_theta_equals_cc(g):
    """
    Test if the Lovasz number of graph ``g`` equals its clique covering number.

    Examples:

        sage: has_lovasz_theta_equals_cc(graphs.CompleteGraph(12))
        True

        sage: has_lovasz_theta_equals_cc(double_fork)
        True

        sage: has_lovasz_theta_equals_cc(graphs.PetersenGraph())
        True

        sage: has_lovasz_theta_equals_cc(Graph(12))
        True

        sage: has_lovasz_theta_equals_cc(graphs.ClebschGraph())
        False

        has_lovasz_theta_equals_alpha(graphs.BuckyBall())
        False

    Edge cases ::

        sage: has_lovasz_theta_equals_cc(Graph(0))
        True

        # Broken. Issue #584
        sage: has_lovasz_theta_equals_cc(Graph(1)) # doctest: +SKIP
        True
    """
    return g.lovasz_theta() == clique_covering_number(g)

def is_chvatal_erdos(g):
    """
    Evaluates whether graph ``g`` meets a Hamiltonicity condition of [CV1972]_.

    OUTPUT:

    Returns ``True`` if the independence number of ``g`` is less than or equal
    to the vertex connectivity of ``g``.
    Returns ``False`` otherwise.

    EXAMPLES:

        sage: is_chvatal_erdos(graphs.CompleteGraph(5))
        True

        sage: is_chvatal_erdos(graphs.CycleGraph(5))
        True

        sage: is_chvatal_erdos(graphs.CompleteGraph(2))
        True

        sage: is_chvatal_erdos(graphs.PetersenGraph())
        False

        sage: is_chvatal_erdos(graphs.ClawGraph())
        False

        sage: is_chvatal_erdos(graphs.DodecahedralGraph())
        False

    Edge cases ::

        sage: is_chvatal_erdos(Graph(1))
        False

        sage: is_chvatal_erdos(Graph(0))
        True

    REFERENCES:

    Theorem: If a graph ``is_chvatal_erdos``, then it is Hamiltonian.

    .. [CV1972]     \V. Chvatal and P. Erdos, "A note on hamiltonian cycles".
                    Discrete Mathematics, 2(2): 111--113, 1972.
    """
    return independence_number(g) <= g.vertex_connectivity()

def matching_covered(g):
    """
    Skipping because broken. See Issue #585.
    """
    g = g.copy()
    nu = matching_number(g)
    E = g.edges()
    for e in E:
        g.delete_edge(e)
        nu2 = matching_number(g)
        if nu != nu2:
            return False
        g.add_edge(e)
    return True

def radius_greater_than_center(g):
    """
    Test if connected graph ``g`` has radius greater than num. of center verts.

    If ``g`` is not connected, returns ``False``.
    Radius is undefined for the empty graph.

    EXAMPLES:

        sage: radius_greater_than_center(graphs.TutteGraph())
        True

        sage: radius_greater_than_center(graphs.KrackhardtKiteGraph())
        True

        sage: radius_greater_than_center(graphs.SousselierGraph())
        True

        sage: radius_greater_than_center(graphs.PetersenGraph())
        False

        sage: radius_greater_than_center(graphs.DiamondGraph())
        False

        sage: radius_greater_than_center(Graph(1))
        False
    """
    return g.is_connected() and g.radius() > card_center(g)

def avg_distance_greater_than_girth(g):
    """
    Tests if graph ``g`` is connected and avg. distance greater than the girth.

    Average distance is undefined for 1- and 0- vertex graphs.

    EXAMPLES:

        sage: avg_distance_greater_than_girth(graphs.TutteGraph())
        True

        sage: avg_distance_greater_than_girth(graphs.HarborthGraph())
        True

        sage: avg_distance_greater_than_girth(graphs.HortonGraph())
        True

        sage: avg_distance_greater_than_girth(graphs.BullGraph())
        False

        sage: avg_distance_greater_than_girth(Graph("NC`@[email protected]_JA??___W"))
        False

        sage: avg_distance_greater_than_girth(Graph(2))
        False

    Acyclic graphs have girth equals infinity. ::

        sage: avg_distance_greater_than_girth(graphs.CompleteGraph(2))
        False
    """
    return g.is_connected() and g.average_distance() > g.girth()

def chi_equals_min_theory(g):
    """
    Evaluate if chromatic num. of graph ``g`` equals min. of some upper bounds.

    Some known upper bounds on the chromatic number Chi (`\chi`) include
    our invariants `[brooks, wilf, welsh_powell, szekeres_wilf]`.
    Returns ``True`` if the actual chromatic number of ``g`` equals the minimum
    of / "the best of" these known upper bounds.

    Some of these invariants are undefined on the empty graph.

    EXAMPLES:

        sage: chi_equals_min_theory(Graph(1))
        True

        sage: chi_equals_min_theory(graphs.PetersenGraph())
        True

        sage: chi_equals_min_theory(double_fork)
        True

        sage: chi_equals_min_theory(Graph(3))
        False

        chi_equals_min_theory(graphs.CompleteBipartiteGraph(3,5))
        False

        chi_equals_min_theory(graphs.IcosahedralGraph())
        False
    """
    chromatic_upper_theory = [brooks, wilf, welsh_powell, szekeres_wilf]
    min_theory = min([f(g) for f in chromatic_upper_theory])
    return min_theory == g.chromatic_number()

def is_heliotropic_plant(g):
    """
    Evaluates whether graph ``g`` is a heliotropic plant. BROKEN

    BROKEN: code should be nonnegative eigen, not just positive eigen.
    See Issue #586

    A graph is heliotropic iff the independence number equals the number of
    nonnegative eigenvalues.

    See [BDF1995]_ for a definition and some related conjectures, where
    [BDF1995]_ builds on the conjecturing work of Siemion Fajtlowicz.

    EXAMPLES:

    REFERENCES:

    .. [BDF1995]    Tony Brewster, Michael J.Dinneen, and Vance Faber, "A
                    computational attack on the conjectures of Graffiti: New
                    counterexamples and proofs". Discrete Mathematics,
                    147(1--3): 35--55, 1995.
    """
    return (independence_number(g) == card_positive_eigenvalues(g))

def is_geotropic_plant(g):
    """
    Evaluates whether graph ``g`` is a heliotropic plant. BROKEN

    BROKEN: code should be nonpositive eigen, not just negative eigen.
    See Issue #586

    A graph is geotropic iff the independence number equals the number of
    nonnegative eigenvalues.

    See [BDF1995]_ for a definition and some related conjectures, where
    [BDF1995]_ builds on the conjecturing work of Siemion Fajtlowicz.

    EXAMPLES:

    REFERENCES:

    .. [BDF1995]    Tony Brewster, Michael J.Dinneen, and Vance Faber, "A
                    computational attack on the conjectures of Graffiti: New
                    counterexamples and proofs". Discrete Mathematics,
                    147(1--3): 35--55, 1995.
    """
    return (independence_number(g) == card_negative_eigenvalues(g))

def is_traceable(g):
    """
    Evaluates whether graph ``g`` is traceable.

    A graph ``g`` is traceable iff there exists a Hamiltonian path, i.e. a path
    which visits all vertices in ``g`` once.
    This is different from ``is_hamiltonian``, since that checks if there
    exists a Hamiltonian *cycle*, i.e. a path which then connects backs to
    its starting point.

    EXAMPLES:

        sage: is_traceable(graphs.CompleteGraph(5))
        True

        sage: is_traceable(graphs.PathGraph(5))
        True

        sage: is_traceable(graphs.PetersenGraph())
        True

        sage: is_traceable(graphs.CompleteGraphs(2))
        True

        sage: is_traceable(Graph(3))
        False

        sage: is_traceable(graphs.ClawGraph())
        False

        sage: is_traceable(graphs.ButterflyGraph())
        False

    Edge cases ::

        sage: is_traceable(Graph(0))
        False

        sage: is_traceable(Graph(1))
        False

    ALGORITHM:

    A graph `G` is traceable iff the join `G'` of `G` with a single new vertex
    `v` is Hamiltonian, where join means to connect every vertex of `G` to the
    new vertex `v`.
    Why? Suppose there exists a Hamiltonian path between `u` and `w` in `G`.
    Then, in `G'`, make a cycle from `v` to `u` to `w` and back to `v`.
    For the reverse direction, just note that the additional vertex `v` cannot
    "help" since Hamiltonian paths can only visit any vertex once.
    """
    gadd = g.join(Graph(1),labels="integers")
    return gadd.is_hamiltonian()

def has_residue_equals_two(g):
    """
    Evaluates whether the residue of graph ``g`` equals 2.

    The residue of a graph ``g`` with degrees `d_1 \geq d_2 \geq ... \geq d_n`
    is found iteratively. First, remove `d_1` from consideration and subtract
    `d_1` from the following `d_1` number of elements. Sort. Repeat this
    process for `d_2,d_3, ...` until only 0s remain. The number of elements,
    i.e. the number of 0s, is the residue of ``g``.

    Residue is undefined on the empty graph.

    EXAMPLES:

        sage: has_residue_equals_two(graphs.ButterflyGraph())
        True

        sage: has_residue_equals_two(graphs.IcosahedralGraph())
        True

        sage: has_residue_equals_two(graphs.OctahedralGraph())
        True

        sage: has_residue_equals_two(Graph(1))
        False

        sage: has_residue_equals_two(graphs.BullGraph())
        False

        sage: has_residue_equals_two(graphs.BrinkmannGraph())
        False
    """
    return residue(g) == 2

def is_chordal_or_not_perfect(g):
    """
    Evaluates if graph ``g`` is either chordal or not perfect.

    There is a known theorem that every chordal graph is perfect.

    OUTPUT:

    Returns ``True`` iff ``g`` is chordal OR (inclusive or) ``g`` is not
    perfect.

    EXAMPLES:

        sage: is_chordal_or_not_perfect(graphs.DiamondGraph())
        True

        sage: is_chordal_or_not_perfect(graphs.CycleGraph(5))
        True

        sage: is_chordal_or_not_perfect(graphs.LollipopGraph(5,3))
        True

        sage: is_chordal_or_not_perfect(graphs.CycleGraph(4))
        False

        sage: is_chordal_or_not_perfect(graphs.HexahedralGraph())
        False

    Vacuously chordal cases ::

        sage: is_chordal_or_not_perfect(Graph(0))
        True

        sage: is_chordal_or_not_perfect(Graph(1))
        True

        sage: is_complement_of_chordal(Graph(4))
        True
    """
    if g.is_chordal():
        return true
    else:
        return not g.is_perfect()

def has_alpha_residue_equal_two(g):
    """
    Tests if both the residue and independence number of graphs ``g`` equal 2.

    The residue of a graph ``g`` with degrees `d_1 \geq d_2 \geq ... \geq d_n`
    is found iteratively. First, remove `d_1` from consideration and subtract
    `d_1` from the following `d_1` number of elements. Sort. Repeat this
    process for `d_2,d_3, ...` until only 0s remain. The number of elements,
    i.e. the number of 0s, is the residue of ``g``.

    Residue is undefined on the empty graph.

    EXAMPLES:

        sage: has_alpha_residue_equal_two(graphs.DiamondGraph())
        True

        sage: has_alpha_residue_equal_two(Graph(2))
        True

        sage: has_alpha_residue_equal_two(graphs.OctahedralGraph())
        True

        sage: has_alpha_residue_equal_two(graphs.BullGraph())
        False

        sage: has_alpha_residue_equal_two(graphs.BidiakisCube())
        False

        sage: has_alpha_residue_equal_two(Graph(3))
        False

        sage: has_alpha_residue_equal_two(Graph(1))
        False
    """
    if residue(g) != 2:
        return false
    else:
        return independence_number(g) == 2

def alpha_leq_order_over_two(g):
    """
    Tests if the independence number of graph ``g`` is at most half its order.

    EXAMPLES:

        sage: alpha_leq_order_over_two(graphs.ButterflyGraph())
        True

        sage: alpha_leq_order_over_two(graphs.DiamondGraph())
        True

        sage: alpha_leq_order_over_two(graphs.CoxeterGraph())
        True

        sage: alpha_leq_order_over_two(Graph(4))
        False

        sage: alpha_leq_order_over_two(graphs.BullGraph())
        False

    Edge cases ::

        sage: alpha_leq_order_over_two(Graph(0))
        True

        sage: alpha_leq_order_over_two(Graph(1))
        False
    """
    return (2*independence_number(g) <= g.order())

def order_leq_twice_max_degree(g):
    """
    Tests if the order of graph ``g`` is at most twice the max of its degrees.

    Undefined for the empty graph.

    EXAMPLES:

        sage: order_leq_twice_max_degree(graphs.BullGraph())
        True

        sage: order_leq_twice_max_degree(graphs.ThomsenGraph())
        True

        sage: order_leq_twice_max_degree(graphs.CycleGraph(4))
        True

        sage: order_leq_twice_max_degree(graphs.BidiakisCube())
        False

        sage: order_leq_twice_max_degree(graphs.CycleGraph(5))
        False

        sage: order_leq_twice_max_degree(Graph(1))
        False
    """
    return (g.order() <= 2*max(g.degree()))

def is_chromatic_index_critical(g):
    """
    Evaluates whether graph ``g`` is chromatic index critical.

    Let `\chi(G)` denote the chromatic index of a graph `G`.
    Then `G` is chromatic index critical if `\chi(G-e) < \chi(G)` (strictly
    less than) for all `e \in G` AND if (by definition) `G` is class 2.

    See [FW1977]_ for a more extended definition and discussion.

    We initially found it surprising that `G` is required to be class 2; for
    example, the Star Graph is a class 1 graph which satisfies the rest of
    the definition. We have found articles which equivalently define critical
    graphs as class 2 graphs which become class 1 when any edge is removed.
    Perhaps this latter definition inspired the one we state above?

    Max degree is undefined on the empty graph, so ``is_class`` is also
    undefined. Therefore this property is undefined on the empty graph.

    EXAMPLES:

        sage: is_chromatic_index_critical(Graph('Djk'))
        True

        sage: is_chromatic_index_critical(graphs.CompleteGraph(3))
        True

        sage: is_chromatic_index_critical(graphs.CycleGraph(5))
        True

        sage: is_chromatic_index_critical(graphs.CompleteGraph(5))
        False

        sage: is_chromatic_index_critical(graphs.PetersenGraph())
        False

        sage: is_chromatic_index_critical(graphs.FlowerSnark())
        False

    Non-trivially disconnected graphs ::

        sage: is_chromatic_index_critical(graphs.CycleGraph(4).disjoint_union(graphs.CompleteGraph(4)))
        False

    Class 1 graphs ::

        sage: is_chromatic_index_critical(Graph(1))
        False

        sage: is_chromatic_index_critical(graphs.CompleteGraph(4))
        False

        sage: is_chromatic_index_critical(graphs.CompleteGraph(2))
        False

        sage: is_chromatic_index_critical(graphs.StarGraph(4))
        False

    ALGORITHM:

    This function uses a series of tricks to reduce the number of cases that
    need to be considered, before finally checking in the obvious way.

    First, if a graph has more than 1 non-trivial connected component, then
    return ``False``. This is because in a graph with multiple such components,
    removing any edges from the smaller component cannot affect the chromatic
    index.

    Second, check if the graph is class 2. If not, stop and return ``False``.

    Finally, identify isomorphic edges using the line graph and its orbits.
    We then need only check the non-equivalent edges to see that they reduce
    the chromatic index when deleted.

    REFERENCES:

    .. [FW1977]     \S. Fiorini and R.J. Wilson, "Edge-colourings of graphs".
                    Pitman Publishing, London, UK, 1977.
    """
    component_sizes = g.connected_components_sizes()
    if len(component_sizes) > 1:
        if component_sizes[1] > 1:
            return False

    if chi == max_degree(g):
        return False

    lg = g.line_graph()
    equiv_lines = lg.automorphism_group(return_group=False, orbits=true)
    equiv_lines_representatives = [orb[0] for orb in equiv_lines]

    gc = g.copy()
    for e in equiv_lines_representatives:
        gc.delete_edge(e)
        chi_prime = gc.chromatic_index()
        if chi_prime == chi:
            return False
        gc.add_edge(e)
    return True

#alpha(g-e) > alpha(g) for *every* edge g
def is_alpha_critical(g):
    #if not g.is_connected():
        #return False
    alpha = independence_number(g)
    for e in g.edges():
        gc = copy(g)
        gc.delete_edge(e)
        alpha_prime = independence_number(gc)
        if alpha_prime <= alpha:
            return False
    return True

#graph is KE if matching number + independence number = n, test does *not* compute alpha
def is_KE(g):
    return g.order() == len(find_KE_part(g))

#graph is KE if matching number + independence number = n, test comoutes alpha
#def is_KE(g):
#    return (g.matching(value_only = True) + independence_number(g) == g.order())

#possibly faster version of is_KE (not currently in invariants)
#def is_KE2(g):
#    return (independence_number(g) == critical_independence_number(g))

def is_independence_irreducible(g):
    return g.order() == card_independence_irreducible_part(g)


def is_factor_critical(g):
    """
    a graph is factor-critical if order is odd and removal of any vertex gives graph with perfect matching
        is_factor_critical(graphs.PathGraph(3))
        False
        sage: is_factor_critical(graphs.CycleGraph(5))
        True
    """
    if g.order() % 2 == 0:
        return False
    for v in g.vertices():
        gc = copy(g)
        gc.delete_vertex(v)
        if not gc.has_perfect_matching:
            return False
    return True

#returns a list of (necessarily non-adjacent) vertices that have the same neighbors as v if a pair exists or None
def find_twins_of_vertex(g,v):
    L = []
    V = g.vertices()
    D = g.distance_all_pairs()
    for i in range(g.order()):
        w = V[i]
        if  D[v][w] == 2 and g.neighbors(v) == g.neighbors(w):
                L.append(w)
    return L

def has_twin(g):
    t = find_twin(g)
    if t == None:
        return False
    else:
        return True

def is_twin_free(g):
    return not has_twin(g)

#returns twin pair (v,w) if one exists, else returns None
#can't be adjacent
def find_twin(g):

    V = g.vertices()
    for v in V:
        Nv = set(g.neighbors(v))
        for w in V:
            Nw = set(g.neighbors(w))
            if v not in Nw and Nv == Nw:
                return (v,w)
    return None

def find_neighbor_twins(g):
    V = g.vertices()
    for v in V:
        Nv = g.neighbors(v)
        for w in Nv:
            if set(closed_neighborhood(g,v)) == set(closed_neighborhood(g,w)):
                return (v,w)
    return None

#given graph g and subset S, looks for any neighbor twin of any vertex in T
#if result = T, then no twins, else the result is maximal, but not necessarily unique
def find_neighbor_twin(g, T):
    gT = g.subgraph(T)
    for v in T:
        condition = False
        Nv = set(g.neighbors(v))
        #print "v = {}, Nv = {}".format(v,Nv)
        NvT = set(gT.neighbors(v))
        for w in Nv:
            NwT = set(g.neighbors(w)).intersection(set(T))
            if w not in T and NvT.issubset(NwT):
                T.append(w)
                condition = True
                #print "TWINS: v = {}, w = {}, sp3 = {}".format(v,w,sp3)
                break
        if condition == True:
            break

#if result = T, then no twins, else the result is maximal, but not necessarily unique
def iterative_neighbor_twins(g, T):
    T2 = copy(T)
    find_neighbor_twin(g, T)
    while T2 != T:
        T2 = copy(T)
        find_neighbor_twin(g, T)
    return T


#can't compute membership in this class directly. instead testing isomorhism for 400 known class0 graphs
def is_pebbling_class0(g):
    for hkey in class0graphs_dict:
        h = Graph(class0graphs_dict[hkey])
        if g.is_isomorphic(h):
            return True
    return False

def girth_greater_than_2log(g):
    return bool(g.girth() > 2*log(g.order(),2))

def szekeres_wilf_equals_chromatic_number(g):
    return szekeres_wilf(g) == g.chromatic_number()

def has_Havel_Hakimi_property(g, v):
    """
    This function returns whether the vertex v in the graph g has the Havel-Hakimi
    property as defined in [1]. A vertex has the Havel-Hakimi property if it has
    maximum degree and the minimum degree of its neighbours is at least the maximum
    degree of its non-neigbours.

    [1] Graphs with the strong Havel-Hakimi property, M. Barrus, G. Molnar, Graphs
        and Combinatorics, 2016, http://dx.doi.org/10.1007/s00373-015-1674-7

    Every vertex in a regular graph has the Havel-Hakimi property::

        sage: P = graphs.PetersenGraph()
        sage: for v in range(10):
        ....:     has_Havel_Hakimi_property(P,v)
        True
        True
        True
        True
        True
        True
        True
        True
        True
        True
        sage: has_Havel_Hakimi_property(Graph([[0,1,2,3],lambda x,y: False]),0)
        True
        sage: has_Havel_Hakimi_property(graphs.CompleteGraph(5),0)
        True
    """
    if max_degree(g) > g.degree(v): return False

    #handle the case where the graph is an independent set
    if len(g.neighbors(v)) == 0: return True

    #handle the case where v is adjacent with all vertices
    if len(g.neighbors(v)) == len(g.vertices()) - 1: return True

    return (min(g.degree(nv) for nv in g.neighbors(v)) >=
        max(g.degree(nnv) for nnv in g.vertices() if nnv != v and nnv not in g.neighbors(v)))

def has_strong_Havel_Hakimi_property(g):
    """
    This function returns whether the graph g has the strong Havel-Hakimi property
    as defined in [1]. A graph has the strong Havel-Hakimi property if in every
    induced subgraph H of G, every vertex of maximum degree has the Havel-Hakimi
    property.

    [1] Graphs with the strong Havel-Hakimi property, M. Barrus, G. Molnar, Graphs
        and Combinatorics, 2016, http://dx.doi.org/10.1007/s00373-015-1674-7

    The graph obtained by connecting two cycles of length 3 by a single edge has
    the strong Havel-Hakimi property::

        sage: has_strong_Havel_Hakimi_property(Graph('E{CW'))
        True
    """
    for S in Subsets(g.vertices()):
        if len(S)>2:
            H = g.subgraph(S)
            Delta = max_degree(H)
            if any(not has_Havel_Hakimi_property(H, v) for v in S if H.degree(v) == Delta):
                return False
    return True

# Graph is subcubic is each vertex is at most degree 3
def is_subcubic(g):
    return max_degree(g) <= 3

# Max and min degree varies by at most 1
def is_quasi_regular(g):
    if max_degree(g) - min_degree(g) < 2:
        return true
    return false

# g is bad if a block is isomorphic to k3, c5, k4*, c5*
def is_bad(g):
    blocks = g.blocks_and_cut_vertices()[0]
    # To make a subgraph of g from the ith block
    for i in blocks:
        h = g.subgraph(i)
        boolean = h.is_isomorphic(alpha_critical_easy[1]) or h.is_isomorphic(alpha_critical_easy[4]) or h.is_isomorphic(alpha_critical_easy[5]) or h.is_isomorphic(alpha_critical_easy[21])
        if boolean == True:
            return True
    return False

# Graph g is complement_hamiltonian if the complement of the graph is hamiltonian.
def is_complement_hamiltonian(g):
    return g.complement().is_hamiltonian()

# A graph is unicyclic if it is connected and has order == size
# Equivalently, graph is connected and has exactly one cycle
def is_unicyclic(g):
    """
    Tests:
        sage: is_unicyclic(graphs.BullGraph())
        True
        sage: is_unicyclic(graphs.ButterflyGraph())
        False
    """
    return g.is_connected() and g.order() == g.size()

def is_k_tough(g,k):
    return toughness(g) >= k # In invariants
def is_1_tough(g):
    return is_k_tough(g, 1)
def is_2_tough(g):
    return is_k_tough(g, 2)

# True if graph has at least two hamiltonian cycles. The cycles may share some edges.
def has_two_ham_cycles(gIn):
    g = gIn.copy()
    g.relabel()
    try:
        ham1 = g.hamiltonian_cycle()
    except EmptySetError:
        return False

    for e in ham1.edges():
        h = copy(g)
        h.delete_edge(e)
        if h.is_hamiltonian():
            return true
    return false

def has_simplical_vertex(g):
    """
    v is a simplical vertex if induced neighborhood is a clique.
    """
    for v in g.vertices():
        if is_simplical_vertex(g, v):
            return true
    return false

def has_exactly_two_simplical_vertices(g):
    """
    v is a simplical vertex if induced neighborhood is a clique.
    """
    return simplical_vertices(g) == 2

def is_two_tree(g):
    """
    Define k-tree recursively:
        - Complete Graph on (k+1)-vertices is a k-tree
        - A k-tree on n+1 vertices is constructed by selecting some k-tree on n vertices and
            adding a degree k vertex such that its open neighborhood is a clique.
    """
    if(g.is_isomorphic(graphs.CompleteGraph(3))):
        return True

    # We can just recurse from any degree-2 vertex; no need to test is_two_tree(g-w) if is_two_tree(g-v) returns False.
    # Intuition why: if neighborhood of a degree-2 v is not a triangle, it won't become one if we remove w (so clique check OK),
    # and, removing a degree-2 vertex of one triangle cannot destroy another triangle (so recursion OK).
    degree_two_vertices = (v for v in g.vertices() if g.degree(v) == 2)
    try:
        v = next(degree_two_vertices)
    except StopIteration: # Empty list. No degree 2 vertices.
        return False

    if not g.has_edge(g.neighbors(v)): # Clique
        return false
    g2 = g.copy()
    g2.delete_vertex(v)
    return is_two_tree(g2)

def is_two_path(g):
    """
    Graph g is a two_path if it is a two_tree and has exactly 2 simplical vertices
    """
    return has_exactly_two_simplical_vertices(g) and is_two_tree(g)

def is_prism_hamiltonian(g):
    """
    A graph G is prism hamiltonian if G x K2 (cartesian product) is hamiltonian
    """
    return g.cartesian_product(graphs.CompleteGraph(2)).is_hamiltonian()

# Bauer, Douglas, et al. "Long cycles in graphs with large degree sums." Discrete Mathematics 79.1 (1990): 59-70.
def is_bauer(g):
    """
    True if g is 2_tough and sigma_3 >= order
    """
    return is_2_tough(g) and sigma_k(g, 3) >= g.order()

# Jung, H. A. "On maximal circuits in finite graphs." Annals of Discrete Mathematics. Vol. 3. Elsevier, 1978. 129-144.
def is_jung(g):
    """
    True if graph has n >= 11, if graph is 1-tough, and sigma_2 >= n - 4.
    See functions toughness(g) and sigma_2(g) for more details.
    """
    return g.order() >= 11 and is_1_tough(g) and sigma_2(g) >= g.order() - 4

# Bela Bollobas and Andrew Thomason, Weakly Pancyclic Graphs. Journal of Combinatorial Theory 77: 121--137, 1999.
def is_weakly_pancyclic(g):
    """
    True if g contains cycles of every length k from k = girth to k = circumfrence

    Returns False if g is acyclic (in which case girth = circumfrence = +Infinity).

    sage: is_weakly_pancyclic(graphs.CompleteGraph(6))
    True
    sage: is_weakly_pancyclic(graphs.PetersenGraph())
    False
    """
    lengths = cycle_lengths(g)
    if not lengths: # acyclic
        raise ValueError("Graph is acyclic. Property undefined.")
    else:
        return lengths == set(range(min(lengths),max(lengths)+1))

def is_pancyclic(g):
    """
    True if g contains cycles of every length from 3 to g.order()

    sage: is_pancyclic(graphs.OctahedralGraph())
    True
    sage: is_pancyclic(graphs.CycleGraph(10))
    False
    """
    lengths = cycle_lengths(g)
    return lengths == set(range(3, g.order()+1))

def has_two_walk(g):
    """
    A two-walk is a closed walk that visits every vertex and visits no vertex more than twice.

    Two-walk is a generalization of Hamiltonian cycles. If a graph is Hamiltonian, then it has a two-walk.

    sage: has_two_walk(c4c4)
    True
    sage: has_two_walk(graphs.WindmillGraph(3,3))
    False
    """
    for init_vertex in g.vertices():
        path_stack = [[init_vertex]]
        while path_stack:
            path = path_stack.pop()
            for neighbor in g.neighbors(path[-1]):
                if neighbor == path[0] and all(v in path for v in g.vertices()):
                    return True
                elif path.count(neighbor) < 2:
                    path_stack.append(path + [neighbor])
    return False

def is_claw_free_paw_free(g):
    return is_claw_free(g) and is_paw_free(g)

def has_bull(g):
    """
    True if g has an induced subgraph isomorphic to graphs.BullGraph()
    """
    return g.subgraph_search(graphs.BullGraph(), induced = True) != None

def is_bull_free(g):
    """
    True if g does not have an induced subgraph isomoprhic to graphs.BullGraph()
    """
    return not has_bull(g)

def is_claw_free_bull_free(g):
    return is_claw_free(g) and is_bull_free(g)

def has_F(g):
    """
    Let F be a triangle with 3 pendants. True if g has an induced F.
    """
    F = graphs.CycleGraph(3)
    F.add_vertices([3,4,5])
    F.add_edges([(0,3), [1,4], [2,5]])
    return g.subgraph_search(F, induced = True) != None

def is_F_free(g):
    """
    Let F be a triangle with 3 pendants. True if g has no induced F.
    """
    return not has_F(g)

# Ronald Gould, Updating the Hamiltonian problem — a survey. Journal of Graph Theory 15.2: 121-157, 1991.
def is_oberly_sumner(g):
    """
    g is_oberly_sumner if order >= 3, is_two_connected, is_claw_free, AND is_F_free
    """
    return g.order() >= 3 and is_two_connected(g) and is_claw_free(g) and is_F_free(g)
def is_oberly_sumner_bull(g):
    """
    True if g is 2-connected, claw-free, and bull-free
    """
    return is_two_connected(g) and is_claw_free_bull_free(g)
def is_oberly_sumner_p4(g):
    """
    True if g is 2-connected, claw-free, and p4-free
    """
    return is_two_connected(g) and is_claw_free(g) and is_p4_free(g)

# Ronald Gould, Updating the Hamiltonian problem — a survey. Journal of Graph Theory 15.2: 121-157, 1991.
def is_matthews_sumner(g):
    """
    True if g is 2-connected, claw-free, and minimum-degree >= (order-1) / 3
    """
    return is_two_connected(g) and is_claw_free(g) and min_degree(g) >= (g.order() - 1) / 3
def is_broersma_veldman_gould(g):
    """
    True if g is 2-connected, claw-free, and diameter <= 2
    """
    return is_two_connected(g) and is_claw_free(g) and g.diameter() <= 2

def chvatals_condition(g):
    """
    True if g.order()>=3 and given increasing degrees d_1,..,d_n, for all i, i>=n/2 or d_i>i or d_{n-i}>=n-1

    This condition is based on Thm 1 of
    Chvátal, Václav. "On Hamilton's ideals." Journal of Combinatorial Theory, Series B 12.2 (1972): 163-168.

    [Chvatal, 72] also showed this condition is sufficient to imply g is Hamiltonian.
    """
    if g.order() < 3:
        return False
    degrees = g.degree()
    degrees.sort()
    n = g.order()
    return all(degrees[i] > i or i >= n/2 or degrees[n-i] >= n-i for i in range(0, len(degrees)))

def is_matching(g):
    """
    Returns True if this graph is the disjoint union of complete graphs of order 2.

    Tests:
        sage: is_matching(graphs.CompleteGraph(2))
        True
        sage: is_matching(graphs.PathGraph(4))
        False
        sage: is_matching(graphs.CompleteGraph(2).disjoint_union(graphs.CompleteGraph(2)))
        True
    """
    return min(g.degree())==1 and max(g.degree())==1

def has_odd_order(g):
    """
    True if the number of vertices in g is odd

    sage: has_odd_order(Graph(5))
    True
    sage: has_odd_order(Graph(2))
    False
    """
    return g.order() % 2 == 1

def has_even_order(g):
    """
    True if the number of vertices in g is even

    sage: has_even_order(Graph(5))
    False
    sage: has_even_order(Graph(2))
    True
    """
    return g.order() % 2 == 0

def is_maximal_triangle_free(g):
    """
    Evaluates whether graphs ``g`` is a maximal triangle-free graph

    Maximal triangle-free means that adding any edge to ``g`` will create a
    triangle.
    If ``g`` is not triangle-free, then returns ``False``.

    EXAMPLES:

        sage: is_maximal_triangle_free(graphs.CompleteGraph(2))
        True

        sage: is_maximal_triangle_free(graphs.CycleGraph(5))
        True

        sage: is_maximal_triangle_free(Graph('Esa?'))
        True

        sage: is_maximal_triangle_free(Graph('KsaCCA?_C?O?'))
        True

        sage: is_maximal_triangle_free(graphs.PathGraph(5))
        False

        sage: is_maximal_triangle_free(Graph('LQY]?cYE_sBOE_'))
        False

        sage: is_maximal_triangle_free(graphs.HouseGraph())
        False

    Edge cases ::

        sage: is_maximal_triangle_free(Graph(0))
        False

        sage: is_maximal_triangle_free(Graph(1))
        False

        sage: is_maximal_triangle_free(Graph(3))
        False
    """
    if not g.is_triangle_free():
        return False
    g_comp = g.complement()
    g_copy = g.copy()
    for e in g_comp.edges():
        g_copy.add_edge(e)
        if g.is_triangle_free():
            return False
        g_copy.delete_edge(e)
    return True

def is_locally_two_connected(g):
    """

    ALGORITHM:

    We modify the algorithm from our ``localise`` factory method to stop at
    subgraphs of 2 vertices, since ``is_two_connected`` is undefined on smaller
    subgraphs.
    """
    return all((f(g.subgraph(g.neighbors(v))) if len(g.neighbors(v)) >= 2
                                              else True) for v in g.vertices())

######################################################################################################################
#Below are some factory methods which create properties based on invariants or other properties

def has_equal_invariants(invar1, invar2, name=None):
    """
    This function takes two invariants as an argument and returns the property that these invariants are equal.
    Optionally a name for the new function can be provided as a third argument.
    """
    def equality_checker(g):
        return invar1(g) == invar2(g)

    if name is not None:
        equality_checker.__name__ = name
    elif hasattr(invar1, '__name__') and hasattr(invar2, '__name__'):
        equality_checker.__name__ = 'has_{}_equals_{}'.format(invar1.__name__, invar2.__name__)
    else:
        raise ValueError('Please provide a name for the new function')

    return equality_checker

"""
    sage: has_alpha_equals_clique_covering(graphs.CycleGraph(5))
    False
"""
has_alpha_equals_clique_covering = has_equal_invariants(independence_number, clique_covering_number, name="has_alpha_equals_clique_covering")


def has_invariant_equal_to(invar, value, name=None, documentation=None):
    """
    This function takes an invariant and a value as arguments and returns the property
    that the invariant value for a graph is equal to the provided value.

    Optionally a name and documentation for the new function can be provided.

    sage: order_is_five = has_invariant_equal_to(Graph.order, 5)
    sage: order_is_five(graphs.CycleGraph(5))
    True
    sage: order_is_five(graphs.CycleGraph(6))
    False
    """
    def equality_checker(g):
        return invar(g) == value

    if name is not None:
        equality_checker.__name__ = name
    elif hasattr(invar, '__name__'):
        equality_checker.__name__ = 'has_{}_equal_to_{}'.format(invar.__name__, value)
    else:
        raise ValueError('Please provide a name for the new function')

    equality_checker.__doc__ = documentation

    return equality_checker

def has_leq_invariants(invar1, invar2, name=None):
    """
    This function takes two invariants as an argument and returns the property that the first invariant is
    less than or equal to the second invariant.
    Optionally a name for the new function can be provided as a third argument.
    """
    def comparator(g):
        return invar1(g) <= invar2(g)

    if name is not None:
        comparator.__name__ = name
    elif hasattr(invar1, '__name__') and hasattr(invar2, '__name__'):
        comparator.__name__ = 'has_{}_leq_{}'.format(invar1.__name__, invar2.__name__)
    else:
        raise ValueError('Please provide a name for the new function')

    return comparator

#add all properties derived from pairs of invariants
invariant_relation_properties = [has_leq_invariants(f,g) for f in all_invariants for g in all_invariants if f != g]


def localise(f, name=None, documentation=None):
    """
    This function takes a property (i.e., a function taking only a graph as an argument) and
    returns the local variant of that property. The local variant is True if the property is
    True for the neighbourhood of each vertex and False otherwise.
    """
    #create a local version of f
    def localised_function(g):
        return all((f(g.subgraph(g.neighbors(v))) if g.neighbors(v) else True) for v in g.vertices())

    #we set a nice name for the new function
    if name is not None:
        localised_function.__name__ = name
    elif hasattr(f, '__name__'):
        if f.__name__.startswith('is_'):
            localised_function.__name__ = 'is_locally' + f.__name__[2:]
        elif f.__name__.startswith('has_'):
            localised_function.__name__ = 'has_locally' + f.__name__[2:]
        else:
            localised_function.__name__ = 'localised_' + f.__name__
    else:
        raise ValueError('Please provide a name for the new function')

    localised_function.__doc__ = documentation

    return localised_function

is_locally_dirac = localise(is_dirac)
is_locally_bipartite = localise(Graph.is_bipartite)
is_locally_planar = localise(Graph.is_planar, documentation="True if the open neighborhood of each vertex v is planar")
"""
Tests:
    sage: is_locally_unicyclic(graphs.OctahedralGraph())
    True
    sage: is_locally_unicyclic(graphs.BullGraph())
    False
"""
is_locally_unicyclic = localise(is_unicyclic, documentation="""A graph is locally unicyclic if all its local subgraphs are unicyclic.

Tests:
    sage: is_locally_unicyclic(graphs.OctahedralGraph())
    True
    sage: is_locally_unicyclic(graphs.BullGraph())
    False
""")
is_locally_connected = localise(Graph.is_connected, documentation="True if the neighborhood of every vertex is connected (stronger than claw-free)")
"""
sage: is_local_matching(graphs.CompleteGraph(3))
True
sage: is_local_matching(graphs.CompleteGraph(4))
False
sage: is_local_matching(graphs.FriendshipGraph(5))
True
"""
is_local_matching = localise(is_matching, name="is_local_matching", documentation="""True if the neighborhood of each vertex consists of independent edges.

Tests:
    sage: is_local_matching(graphs.CompleteGraph(3))
    True
    sage: is_local_matching(graphs.CompleteGraph(4))
    False
    sage: is_local_matching(graphs.FriendshipGraph(5))
    True
""")

######################################################################################################################

efficiently_computable_properties = [Graph.is_regular, Graph.is_planar,
Graph.is_forest, Graph.is_eulerian, Graph.is_connected, Graph.is_clique,
Graph.is_circular_planar, Graph.is_chordal, Graph.is_bipartite,
Graph.is_cartesian_product,Graph.is_distance_regular,  Graph.is_even_hole_free,
Graph.is_gallai_tree, Graph.is_line_graph, Graph.is_overfull, Graph.is_perfect,
Graph.is_split, Graph.is_strongly_regular, Graph.is_triangle_free,
Graph.is_weakly_chordal, is_dirac, is_ore,
is_generalized_dirac, is_van_den_heuvel, is_two_connected, is_three_connected,
is_lindquester, is_claw_free, Graph.has_perfect_matching, has_radius_equal_diameter,
is_not_forest, is_genghua_fan, is_cubic, diameter_equals_twice_radius,
is_locally_connected, matching_covered, is_locally_dirac,
is_locally_bipartite, is_locally_two_connected, Graph.is_interval, has_paw,
is_paw_free, has_p4, is_p4_free, has_dart, is_dart_free, has_kite, is_kite_free,
has_H, is_H_free, has_residue_equals_two, order_leq_twice_max_degree,
alpha_leq_order_over_two, is_factor_critical, is_independence_irreducible,
has_twin, is_twin_free, diameter_equals_two, girth_greater_than_2log, Graph.is_cycle,
pairs_have_unique_common_neighbor, has_star_center, is_complement_of_chordal,
has_c4, is_c4_free, is_subcubic, is_quasi_regular, is_bad, has_k4, is_k4_free,
is_distance_transitive, is_unicyclic, is_locally_unicyclic, has_simplical_vertex,
has_exactly_two_simplical_vertices, is_two_tree, is_locally_planar,
is_four_connected, is_claw_free_paw_free, has_bull, is_bull_free,
is_claw_free_bull_free, has_F, is_F_free, is_oberly_sumner, is_oberly_sumner_bull,
is_oberly_sumner_p4, is_matthews_sumner, chvatals_condition, is_matching, is_local_matching,
has_odd_order, has_even_order, Graph.is_circulant, Graph.has_loops,
Graph.is_asteroidal_triple_free, Graph.is_block_graph, Graph.is_cactus,
Graph.is_cograph, Graph.is_long_antihole_free, Graph.is_long_hole_free, Graph.is_partial_cube,
Graph.is_polyhedral, Graph.is_prime, Graph.is_tree, Graph.is_apex, Graph.is_arc_transitive,
Graph.is_self_complementary, is_double_clique, has_fork, is_fork_free,
has_empty_KE_part]

intractable_properties = [Graph.is_hamiltonian, Graph.is_vertex_transitive,
Graph.is_edge_transitive, has_residue_equals_alpha, Graph.is_odd_hole_free,
Graph.is_semi_symmetric, is_planar_transitive, is_class1,
is_class2, is_anti_tutte, is_anti_tutte2, has_lovasz_theta_equals_cc,
has_lovasz_theta_equals_alpha, is_chvatal_erdos, is_heliotropic_plant,
is_geotropic_plant, is_traceable, is_chordal_or_not_perfect,
has_alpha_residue_equal_two, is_complement_hamiltonian, is_1_tough, is_2_tough,
has_two_ham_cycles, is_two_path, is_prism_hamiltonian, is_bauer, is_jung,
is_weakly_pancyclic, is_pancyclic, has_two_walk, has_alpha_equals_clique_covering,
Graph.is_transitively_reduced, Graph.is_half_transitive, Graph.is_line_graph,
is_haggkvist_nicoghossian, is_chromatic_index_critical]

removed_properties = [is_pebbling_class0]

"""
    Last version of graphs packaged checked: Sage 8.2
    This means checked for new functions, and for any errors/changes in old functions!
    sage: sage.misc.banner.version_dict()['major'] < 8 or (sage.misc.banner.version_dict()['major'] == 8 and sage.misc.banner.version_dict()['minor'] <= 2)
    True

    Skip Graph.is_circumscribable() and Graph.is_inscribable() because they
        throw errors for the vast majority of our graphs.
    Skip Graph.is_biconnected() in favor of our is_two_connected(), because we
        prefer our name, and because we disagree with their definition on K2.
        We define that K2 is NOT 2-connected, it is n-1 = 1 connected.
    Implementation of Graph.is_line_graph() is intractable, despite a theoretically efficient algorithm existing.
"""
sage_properties = [Graph.is_hamiltonian, Graph.is_eulerian, Graph.is_planar,
Graph.is_circular_planar, Graph.is_regular, Graph.is_chordal, Graph.is_circulant,
Graph.is_interval, Graph.is_gallai_tree, Graph.is_clique, Graph.is_cycle,
Graph.is_transitively_reduced, Graph.is_self_complementary, Graph.is_connected,
Graph.has_loops, Graph.is_asteroidal_triple_free, Graph.is_bipartite,
Graph.is_block_graph, Graph.is_cactus, Graph.is_cartesian_product,
Graph.is_cograph, Graph.is_distance_regular, Graph.is_edge_transitive, Graph.is_even_hole_free,
Graph.is_forest, Graph.is_half_transitive, Graph.is_line_graph,
Graph.is_long_antihole_free, Graph.is_long_hole_free, Graph.is_odd_hole_free,
Graph.is_overfull, Graph.is_partial_cube, Graph.is_polyhedral, Graph.is_prime,
Graph.is_semi_symmetric, Graph.is_split, Graph.is_strongly_regular, Graph.is_tree,
Graph.is_triangle_free, Graph.is_weakly_chordal, Graph.has_perfect_matching, Graph.is_apex,
Graph.is_arc_transitive]

#speed notes
#FAST ENOUGH (tested for graphs on 140921): is_hamiltonian, is_vertex_transitive,
#    is_edge_transitive, has_residue_equals_alpha, is_odd_hole_free, is_semi_symmetric,
#    is_line_graph, is_line_graph, is_anti_tutte, is_planar_transitive
#SLOW but FIXED for SpecialGraphs: is_class1, is_class2

properties = efficiently_computable_properties + intractable_properties
properties_plus = efficiently_computable_properties + intractable_properties + invariant_relation_properties


invariants_from_properties = [make_invariant_from_property(property) for property in properties]
invariants_plus = all_invariants + invariants_from_properties

# weakly_chordal = weakly chordal, i.e., the graph and its complement have no induced cycle of length at least 5

print("loaded properties")

#############################################################################
# End of properties section                                                 #
#############################################################################
# THEORY
all_invariant_theorems = []
all_property_theorems = []

alpha_upper_bounds = []
alpha_lower_bounds = []

hamiltonian_sufficient = []

#####
# ALPHA UPPER BOUNDS
#####

# R. Pepper. Binding independence. Ph. D. Dissertation. University of Houston. Houston, TX, 2004.
alpha_annihilation_bound = annihilation_number
add_to_lists(alpha_annihilation_bound, alpha_upper_bounds, all_invariant_theorems)

# Nemhauser, George L., and Leslie Earl Trotter. "Vertex packings: structural properties and algorithms." Mathematical Programming 8.1 (1975): 232-248.
# Nemhauser, George L., and Leslie E. Trotter. "Properties of vertex packing and independence system polyhedra." Mathematical Programming 6.1 (1974): 48-61.
alpha_fractional_bound = fractional_alpha
add_to_lists(alpha_fractional_bound, alpha_upper_bounds, all_invariant_theorems)

# D. M. Cvetkovic, M. Doob, and H. Sachs. Spectra of graphs. Academic Press, New York, 1980.
alpha_cvetkovic_bound = cvetkovic
add_to_lists(alpha_cvetkovic_bound, alpha_upper_bounds, all_invariant_theorems)

# Trivial
alpha_trivial_bound = Graph.order
add_to_lists(alpha_trivial_bound, alpha_upper_bounds, all_invariant_theorems)

# Lovasz Theta
alpha_lovasz_theta_bound = Graph.lovasz_theta
add_to_lists(alpha_lovasz_theta_bound, alpha_upper_bounds, all_invariant_theorems)

# R. Pepper. Binding independence. Ph. D. Dissertation. University of Houston. Houston, TX, 2004.
def alpha_kwok_bound(g):
    return order(g) - (g.size()/max_degree(g))
add_to_lists(alpha_kwok_bound, alpha_upper_bounds, all_invariant_theorems)

# P. Hansen and M. Zheng. Sharp Bounds on the order, size, and stability number of graphs. NETWORKS 23 (1993), no. 2, 99-102.
def alpha_hansen_bound(g):
    return floor(1/2 + sqrt(1/4 + order(g)**2 - order(g) - 2*size(g)))
add_to_lists(alpha_hansen_bound, alpha_upper_bounds, all_invariant_theorems)

# Matching Number - Folklore
def alpha_matching_number_bound(g):
    return order(g) - matching_number(g)
add_to_lists(alpha_matching_number_bound, alpha_upper_bounds, all_invariant_theorems)

# Min-Degree Theorm
def alpha_min_degree_bound(g):
    return order(g) - min_degree(g)
add_to_lists(alpha_min_degree_bound, alpha_upper_bounds, all_invariant_theorems)

# Cut Vertices Theorem
# Three Bounds on the Independence Number of a Graph - C. E. Larson, R. Pepper
def alpha_cut_vertices_bound(g):
    return (g.order() - (card_cut_vertices(g)/2) - (1/2))
add_to_lists(alpha_cut_vertices_bound, alpha_upper_bounds, all_invariant_theorems)

# Median Degree Theorem
# Three Bounds on the Independence Number of a Graph - C. E. Larson, R. Pepper
def alpha_median_degree_bound(g):
    return (g.order() - (median_degree(g)/2) - 1/2)
add_to_lists(alpha_median_degree_bound, alpha_upper_bounds, all_invariant_theorems)

# Godsil-Newman Upper Bound theorem
# Godsil, Chris D., and Mike W. Newman. "Eigenvalue bounds for independent sets." Journal of Combinatorial Theory, Series B 98.4 (2008): 721-734.
def alpha_godsil_newman_bound(g):
    L = max(g.laplacian_matrix().change_ring(RDF).eigenvalues())
    return g.order()*(L-min_degree(g))/L
add_to_lists(alpha_godsil_newman_bound, alpha_upper_bounds, all_invariant_theorems)

# AGX Upper Bound Theorem
#Aouchiche, Mustapha, Gunnar Brinkmann, and Pierre Hansen. "Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number." Discrete Applied Mathematics 156.13 (2008): 2530-2542.
def alpha_AGX_upper_bound(g):
    return (g.order() + max_degree(g) - ceil(2 * sqrt(g.order() - 1)))
add_to_lists(alpha_AGX_upper_bound, alpha_upper_bounds, all_invariant_theorems)

def alpha_li_zhang_1_bound(g):
    """
    From:
    A note on eigenvalue bounds for independence numbers of non-regular graphs
    By Yusheng Li, Zhen Zhang
    """
    return (((max_degree(g)) - min_degree(g) - min_eigenvalue(g)) / max_degree(g)) * g.order()
add_to_lists(alpha_li_zhang_1_bound, alpha_upper_bounds, all_invariant_theorems)

def alpha_li_zhang_2_bound(g):
    """
    From:
    A note on eigenvalue bounds for independence numbers of non-regular graphs
    By Yusheng Li, Zhen Zhang
    """
    return ((max_eigenvalue(g) - min_eigenvalue(g) + max_degree(g) - 2 * min_degree(g)) / (max_eigenvalue(g) - min_eigenvalue(g) + max_degree(g) - min_degree(g))) * g.order()
add_to_lists(alpha_li_zhang_2_bound, alpha_upper_bounds, all_invariant_theorems)

def alpha_haemers_bound(g):
    """
    From: W. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 226/228 (1995) 593–616.
    """
    return ((-max_eigenvalue(g) * min_eigenvalue(g)) / (min_degree(g)**2 - (max_eigenvalue(g) * min_eigenvalue(g)))) * g.order()
add_to_lists(alpha_haemers_bound, alpha_upper_bounds, all_invariant_theorems)

#####
# LOWER BOUNDS
#####

# Radius Pendants Theorem
# Three Bounds on the Independence Number of a Graph - C. E. Larson, R. Pepper
def alpha_radius_pendants_bound(g):
    return (g.radius() + (card_pendants(g)/2) - 1)
add_to_lists(alpha_radius_pendants_bound, alpha_lower_bounds, all_invariant_theorems)

# AGX Lower Bound Theorem
# Aouchiche, Mustapha, Gunnar Brinkmann, and Pierre Hansen. "Variable neighborhood search for extremal graphs. 21. Conjectures and results about the independence number." Discrete Applied Mathematics 156.13 (2008): 2530-2542.
def alpha_AGX_lower_bound(g):
    return ceil(2 * sqrt(g.order()))
add_to_lists(alpha_AGX_lower_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_max_degree_minus_triangles_bound(g):
    return max_degree(g) - g.triangles_count()
add_to_lists(alpha_max_degree_minus_triangles_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_order_brooks_bound(g):
    return ceil(g.order()/brooks(g))
add_to_lists(alpha_order_brooks_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_szekeres_wilf_bound(g):
    return ceil(g.order()/szekeres_wilf(g))
add_to_lists(alpha_szekeres_wilf_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_welsh_powell_bound(g):
    return ceil(g.order()/welsh_powell(g))
add_to_lists(alpha_welsh_powell_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_staton_girth_bound(g):
    """
    Hopkins, Glenn, and William Staton. "Girth and independence ratio." Can. Math. Bull. 25.2 (1982): 179-186.
    """
    if g.girth() < 6:
        return 1
    else:
        d = max_degree(g)
        return order(g) * (2* d - 1) / (d*d + 2 * d - 1)
add_to_lists(alpha_staton_girth_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_staton_triangle_free_bound(g):
    """
    Staton, William. "Some Ramsey-type numbers and the independence ratio." Transactions of the American Mathematical Society 256 (1979): 353-370.
    """
    if g.is_triangle_free() and (max_degree(g) > 2):
        return (5 * g.order() ) / ((5 * max_degree(g)) - 1)
    return 1
add_to_lists(alpha_staton_triangle_free_bound, alpha_lower_bounds, all_invariant_theorems)

alpha_average_distance_bound = Graph.average_distance
add_to_lists(alpha_average_distance_bound, alpha_lower_bounds, all_invariant_theorems)

alpha_radius_bound = Graph.radius
add_to_lists(alpha_radius_bound, alpha_lower_bounds, all_invariant_theorems)

alpha_residue_bound = residue
add_to_lists(alpha_residue_bound, alpha_lower_bounds, all_invariant_theorems)

alpha_max_even_minus_even_horizontal_bound = max_even_minus_even_horizontal
add_to_lists(alpha_max_even_minus_even_horizontal_bound, alpha_lower_bounds, all_invariant_theorems)

alpha_critical_independence_number_bound = critical_independence_number
add_to_lists(alpha_critical_independence_number_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_max_degree_minus_number_of_triangles_bound(g):
    return max_degree(g) - g.triangles_count()
add_to_lists(alpha_max_degree_minus_number_of_triangles_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_HHRS_bound(g):
    """
    Returns 1 if max_degree > 3 or if g has k4 as a subgraph
    ONLY WORKS FOR CONNECTED GRAPHS becasue that is what we are focussing on, disconnected graphs just need to count the bad compenents

    Harant, Jochen, et al. "The independence number in graphs of maximum degree three." Discrete Mathematics 308.23 (2008): 5829-5833.
    """
    assert(g.is_connected() == true)
    if not is_subcubic(g):
        return 1
    if has_k4(g):
        return 1
    return (4*g.order() - g.size() - (1 if is_bad(g) else 0) - subcubic_tr(g)) / 7
add_to_lists(alpha_HHRS_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_seklow_bound(g):
    """
    Returns the Seklow bound from:
    Selkow, Stanley M. "A probabilistic lower bound on the independence number of graphs." Discrete Mathematics 132.1-3 (1994): 363-365.
    """
    v_sum = 0
    for v in g.vertices():
        d = g.degree(v)
        v_sum += ((1/(d + 1)) * (1 + max(0, (d/(d + 1) - sum([(1/(g.degree(w) + 1)) for w in g.neighbors(v)])))))
    return v_sum
add_to_lists(alpha_seklow_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_harant_bound(g):
    """
    From:
    A lower bound on the independence number of a graph
    Jochen Harant
    """
    return (caro_wei(g)**2) / (caro_wei(g) - sum([(g.degree(e[0]) - g.degree(e[1]))**2 * (1/g.degree(e[0]))**2 * (1/g.degree(e[1]))**2 for e in g.edges()]))
add_to_lists(alpha_harant_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_harant_schiermeyer_bound(g):
    """
    From:
    On the independence number of a graph in terms of order and size
    By J. Harant and I. Schiermeyerb
    """
    order = g.order()
    t = 2*g.size() + order + 1
    return (t - sqrt(t**2 - 4 * order**2)) / 2
add_to_lists(alpha_harant_schiermeyer_bound, alpha_lower_bounds, all_invariant_theorems)

def alpha_shearer_bound(g):
    """
    From:
    Shearer, James B. "The independence number of dense graphs with large odd girth." Electron. J. Combin 2.2 (1995).
    """
    girth = g.girth()

    if girth == +Infinity:
        return 1.0
    if is_even(girth):
        return 1.0

    k = ((girth - 1) / 2.0)
    v_sum = sum([g.degree(v)**(1/(k - 1.0)) for v in g.vertices()])
    return 2**(-((k - 1.0)/k)) * v_sum**((k - 1.0)/k)
add_to_lists(alpha_shearer_bound, alpha_lower_bounds, all_invariant_theorems)


####
# HAMILTONICITY SUFFICIENT CONDITIONS
####
# Chvátal, V., & Erdös, P. (1972). A note on hamiltonian circuits. Discrete Mathematics, 2(2), 111-113.
add_to_lists(is_chvatal_erdos, hamiltonian_sufficient, all_property_theorems)

# R.J Faudree, Ronald J Gould, Michael S Jacobson, R.H Schelp, Neighborhood unions and hamiltonian properties in graphs, Journal of Combinatorial Theory, Series B, Volume 47, Issue 1, 1989, Pages 1-9
add_to_lists(is_generalized_dirac, hamiltonian_sufficient, all_property_theorems)

# Häggkvist, Roland & Nicoghossian, G. G. (1981). A remark on hamiltonian cycles. Journal of Combinatorial Theory, 30(1), 118-120
add_to_lists(is_haggkvist_nicoghossian, hamiltonian_sufficient, all_property_theorems)

# Fan, G. H. (1984). New sufficient conditions for cycles in graphs. Journal of Combinatorial Theory, 37(3), 221-227.
add_to_lists(is_genghua_fan, hamiltonian_sufficient, all_property_theorems)

# Lindquester, T. E. (1989). The effects of distance and neighborhood union conditions on hamiltonian properties in graphs. Journal of Graph Theory, 13(3), 335-352.
# Ore, Ø. (1960), "Note on Hamilton circuits", American Mathematical Monthly, 67 (1): 55, doi:10.2307/2308928, JSTOR 2308928.
def is_lindquester_or_is_ore(g):
    return is_lindquester(g) or is_ore(g)
add_to_lists(is_lindquester_or_is_ore, hamiltonian_sufficient, all_property_theorems)

# Trivial / "belongs to folklore"
def is_cycle_or_is_clique(g):
    return is_cycle(g) or g.is_clique()
add_to_lists(is_cycle_or_is_clique, hamiltonian_sufficient, all_property_theorems)

# Geng-Hua Fan. "New Sufficient Conditions for Cycles in Graphs". Journal of Combinatorial Theory 37.3(1984):221-227.
def sigma_dist2_geq_half_n(g):
    return sigma_dist2(g) >= g.order()/2
add_to_lists(sigma_dist2_geq_half_n, hamiltonian_sufficient, all_property_theorems)

# Bauer, Douglas, et al. "Long cycles in graphs with large degree sums." Discrete Mathematics 79.1 (1990): 59-70.
add_to_lists(is_bauer, hamiltonian_sufficient, all_property_theorems)

# Jung, H. A. "On maximal circuits in finite graphs." Annals of Discrete Mathematics. Vol. 3. Elsevier, 1978. 129-144.
add_to_lists(is_jung, hamiltonian_sufficient, all_property_theorems)

# S. Goodman and S. Hedetniemi, Sufficient Conditions for a Graph to Be Hamiltonian. Journal of Combinatorial Theory 16: 175--180, 1974.
def is_two_connected_claw_free_paw_free(g):
    return is_two_connected(g) and is_claw_free_paw_free(g)
add_to_lists(is_claw_free_paw_free, hamiltonian_sufficient, all_property_theorems)

# Ronald Gould, Updating the Hamiltonian problem — a survey. Journal of Graph Theory 15.2: 121-157, 1991.
add_to_lists(is_oberly_sumner, hamiltonian_sufficient, all_property_theorems)
add_to_lists(is_oberly_sumner_bull, hamiltonian_sufficient, all_property_theorems)
add_to_lists(is_oberly_sumner_p4, hamiltonian_sufficient, all_property_theorems)
add_to_lists(is_matthews_sumner, hamiltonian_sufficient, all_property_theorems)
add_to_lists(is_broersma_veldman_gould, hamiltonian_sufficient, all_property_theorems)

# Chvátal, Václav. "On Hamilton's ideals." Journal of Combinatorial Theory, Series B 12.2 (1972): 163-168.
add_to_lists(chvatals_condition, hamiltonian_sufficient, all_property_theorems)


####
# HAMILTONICITY NECESSARY CONDITIONS
####

print("loaded theorems")

#############################################################################
# End of theorems section                                                   #
#############################################################################
# Graph Lists

graph_objects = []
alpha_critical_easy = []
alpha_critical_hard = []
chromatic_index_critical = []
chromatic_index_critical_7 = []
class0graphs = []
class0small = []
counter_examples = []
problem_graphs = []
sloane_graphs = []
non_connected_graphs = []
dimacs_graphs = []
all_graphs = []

# HexahedralGraph is CE to (((is_planar)&(is_regular))&(is_bipartite))->(has_residue_equals_alpha)
# WagnerGraph is a graph for which the Cvetkovic bound is the best upper bound present in the Willis Thesis
# OctohedralGraph is a graph for which the minimum degree is the best upper bound present in the Willis thesis
# BidiakisCube is a graph where none of the upper or lower bounds in the Willis thesis give the exact value for alpha
# TetrahedralGraph and MoserSpindle in the alpha critical list as "C~" and "FzEKW" respectively
# MeredithGraph and SchlaefliGraph are in the Problem Graphs list

sage_graphs = [graphs.BullGraph(), graphs.ButterflyGraph(), graphs.ClawGraph(),
graphs.DiamondGraph(), graphs.HouseGraph(), graphs.HouseXGraph(), graphs.Balaban10Cage(),
graphs.Balaban11Cage(), graphs.BidiakisCube(),
graphs.BiggsSmithGraph(), graphs.BlanusaFirstSnarkGraph(), graphs.BlanusaSecondSnarkGraph(),
graphs.BrinkmannGraph(), graphs.BrouwerHaemersGraph(), graphs.BuckyBall(),
graphs.ChvatalGraph(), graphs.ClebschGraph(),
graphs.CoxeterGraph(), graphs.DesarguesGraph(), graphs.DejterGraph(), graphs.DoubleStarSnark(),
graphs.DurerGraph(), graphs.DyckGraph(), graphs.EllinghamHorton54Graph(),
graphs.EllinghamHorton78Graph(), graphs.ErreraGraph(), graphs.F26AGraph(), graphs.FlowerSnark(),
graphs.FolkmanGraph(), graphs.FosterGraph(), graphs.FranklinGraph(), graphs.FruchtGraph(),
graphs.GoldnerHararyGraph(), graphs.GossetGraph(), graphs.GrayGraph(), graphs.GrotzschGraph(),
graphs.HallJankoGraph(), graphs.HarborthGraph(), graphs.HarriesGraph(), graphs.HarriesWongGraph(),
graphs.HeawoodGraph(), graphs.HerschelGraph(), graphs.HigmanSimsGraph(), graphs.HoffmanGraph(),
graphs.HoffmanSingletonGraph(), graphs.HoltGraph(), graphs.HortonGraph(), graphs.JankoKharaghaniTonchevGraph(), graphs.KittellGraph(),
graphs.KrackhardtKiteGraph(), graphs.Klein3RegularGraph(), graphs.Klein7RegularGraph(),
graphs.LjubljanaGraph(),
graphs.MarkstroemGraph(), graphs.McGeeGraph(),
graphs.MoebiusKantorGraph(), graphs.NauruGraph(), graphs.PappusGraph(),
graphs.PoussinGraph(), graphs.PerkelGraph(), graphs.PetersenGraph(), graphs.RobertsonGraph(),
graphs.ShrikhandeGraph(), graphs.SimsGewirtzGraph(),
graphs.SousselierGraph(), graphs.SylvesterGraph(), graphs.SzekeresSnarkGraph(),
graphs.ThomsenGraph(), graphs.TietzeGraph(),
graphs.TruncatedTetrahedralGraph(), graphs.Tutte12Cage(), graphs.TutteCoxeterGraph(),
graphs.TutteGraph(), graphs.WagnerGraph(), graphs.WatkinsSnarkGraph(), graphs.WellsGraph(),
graphs.WienerArayaGraph(),
graphs.HexahedralGraph(), graphs.DodecahedralGraph(), graphs.OctahedralGraph(), graphs.IcosahedralGraph()]

try:
    add_to_lists(graphs.CameronGraph(), sage_graphs)
except Exception as e:
    print("The Cameron graph was not loaded. Caused by:")
    print(e)

try:
    add_to_lists(graphs.M22Graph(), sage_graphs)
except Exception as e:
    print("The M22 graph was not loaded. Caused by:")
    print(e)

try:
    add_to_lists(graphs.TruncatedIcosidodecahedralGraph(), sage_graphs)
except Exception as e:
    print("The truncated icosidodecahedral graph was not loaded. Caused by:")
    print(e)

try:
    add_to_lists(graphs.McLaughlinGraph(), sage_graphs)
except Exception as e:
    print("The McLaughlin graph was not loaded. Caused by:")
    print(e)

try:
    add_to_lists(graphs.LocalMcLaughlinGraph(), sage_graphs)
except Exception as e:
    print("The local McLaughlin graph was not loaded. Caused by:")
    print(e)

#hard built-in Sage graphs
add_to_lists(graphs.IoninKharaghani765Graph(), problem_graphs, all_graphs)


#These built in graphs are nameless so here they are given names

try:
    cell120 = graphs.Cell120()
    cell120.name(new = "Cell120")
    add_to_lists(cell120, sage_graphs)
except Exception as e:
    print("The graph of the 120-cell was not loaded. Caused by:")
    print(e)

try:
    cell600 = graphs.Cell600()
    cell600.name(new = "Cell600")
    add_to_lists(cell600, sage_graphs)
except Exception as e:
    print("The graph of the 600-cell was not loaded. Caused by:")
    print(e)

mathon_strongly_regular0 = graphs.MathonStronglyRegularGraph(0)
mathon_strongly_regular0.name(new = "Mathon Strongly Regular Graph 0")

mathon_strongly_regular1 = graphs.MathonStronglyRegularGraph(1)
mathon_strongly_regular1.name(new = "Mathon Strongly Regular Graph 1")

mathon_strongly_regular2 = graphs.MathonStronglyRegularGraph(2)
mathon_strongly_regular2.name(new = "Mathon Strongly Regular Graph 2")

janko_kharaghani936 = graphs.JankoKharaghaniGraph(936)
janko_kharaghani936.name(new = "Janko-Kharaghani 936")

# janko_kharaghani1800 = graphs.JankoKharaghaniGraph(1800) # Causes memory error when doctesting. Waiting for fix in Sage.
# janko_kharaghani1800.name(new = "Janko-Kharagani 1800")

for graph in sage_graphs + [mathon_strongly_regular0, mathon_strongly_regular1, mathon_strongly_regular2, janko_kharaghani936]:
    add_to_lists(graph, graph_objects, all_graphs)

# Meredith graph is 4-reg, class2, non-hamiltonian: http://en.wikipedia.org/wiki/Meredith_graph
add_to_lists(graphs.MeredithGraph(), problem_graphs, all_graphs)
add_to_lists(graphs.SchlaefliGraph(), problem_graphs, all_graphs)

# A graph is alpha_critical if removing any edge increases independence number
# All alpha critical graphs of orders 2 to 9, 53 in total

# "E|OW" is CE to (has_alpha_residue_equal_two)->((is_perfect)|(is_regular))

alpha_critical_graph_names = ['A_','Bw', 'C~', 'Dhc', 'D~{', 'E|OW', 'E~~w', 'FhCKG', 'F~[KG',
'FzEKW', 'Fn[kG', 'F~~~w', 'GbL|TS', 'G~?mvc', 'GbMmvG', 'Gb?kTG', 'GzD{Vg', 'Gb?kR_', 'GbqlZ_',
'GbilZ_', 'G~~~~{', 'GbDKPG', 'HzCGKFo', 'H~|wKF{', 'HnLk]My', 'HhcWKF_', 'HhKWKF_', 'HhCW[F_',
'HxCw}V`', 'HhcGKf_', 'HhKGKf_', 'Hh[gMEO', 'HhdGKE[', 'HhcWKE[', 'HhdGKFK', '[email protected]', 'Hn[[email protected]',
'Hn^[email protected]', 'HlDKhEH', 'H~~~~~~', 'HnKmH]N', 'HnvzhEH', '[email protected]', '[email protected]', 'Hj~KHeF', 'HhdGHeB',
'HhXg[EO', 'HhGG]ES', 'H~Gg]f{', 'H~?g]vs', '[email protected][Vs', 'Hn_k[^o']

for s in alpha_critical_graph_names:
    g = Graph(s)
    g.name(new="alpha_critical_"+ s)
    add_to_lists(g, alpha_critical_easy, graph_objects, all_graphs)

# All order-7 chromatic_index_critical_graphs (and all are overfull)
n7_chromatic_index_critical_names = ['FhCKG', 'FzCKW', 'FzNKW', 'FlSkG', 'Fn]kG', 'FlLKG', 'FnlkG', 'F~|{G', 'FnlLG', 'F~|\\G',
'FnNLG', 'F~^LW', 'Fll\\G', 'FllNG', 'F~l^G', 'F~|^w', 'F~~^W', 'Fnl^W', 'FlNNG', 'F|\\Kg',
'F~^kg', 'FlKMG']

for s in n7_chromatic_index_critical_names:
    g=Graph(s)
    g.name(new="chromatic_index_critical_7_" + s)
    add_to_lists(g, chromatic_index_critical, chromatic_index_critical_7, problem_graphs, all_graphs)

alpha_critical_hard = [Graph('Hj\\x{F{')]
for g in alpha_critical_hard:
    add_to_lists(g, problem_graphs, all_graphs)

# Graph objects

p3 = graphs.PathGraph(3)
p3.name(new = "p3")
add_to_lists(p3, graph_objects, all_graphs)

p4 = graphs.PathGraph(4)
p4.name(new="p4")
add_to_lists(p4, graph_objects, all_graphs)

p5 = graphs.PathGraph(5)
p5.name(new = "p5")
add_to_lists(p5, graph_objects, all_graphs)

p6 = graphs.PathGraph(6)
p6.name(new="p6")
add_to_lists(p6, graph_objects, all_graphs)

"""
CE to independence_number(x) <= e^(cosh(max_degree(x) - 1))
 and to
independence_number(x) <= max_degree(x)*min_degree(x) + card_periphery(x)
"""
p9 = graphs.PathGraph(9)
p9.name(new = "p9")
add_to_lists(p9, graph_objects, counter_examples, all_graphs)

"""
P29 is a CE to independence_number(x) <=degree_sum(x)/sqrt(card_negative_eigenvalues(x))
 and to
<= max_degree(x)^e^card_center(x)
 and to
<= max_degree(x)^2 + card_periphery(x)
"""
p29 = graphs.PathGraph(29)
p29.name(new = "p29")
add_to_lists(p29, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= 2*cvetkovic(x)*log(10)/log(x.size())
p102 = graphs.PathGraph(102)
p102.name(new = "p102")
add_to_lists(p102, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x)<=welsh_powell(x)^e^different_degrees(x)
p6707 = graphs.PathGraph(6707)
p6707.name(new = "p6707")

c4 = graphs.CycleGraph(4)
c4.name(new="c4")
add_to_lists(c4, graph_objects, all_graphs)

c6 = graphs.CycleGraph(6)
c6.name(new = "c6")
add_to_lists(c6, graph_objects, all_graphs)

# CE to independence_number(x) <= (e^welsh_powell(x) - graph_rank(x))^2
c22 = graphs.CycleGraph(22)
c22.name(new = "c22")
add_to_lists(c22, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= minimum(cvetkovic(x), 2*e^sum_temperatures(x))
c34 = graphs.CycleGraph(34)
c34.name(new = "c34")
add_to_lists(c34, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= residue(x)^(degree_sum(x)^density(x))
c102 = graphs.CycleGraph(102)
c102.name(new = "c102")
add_to_lists(c102, graph_objects, counter_examples, all_graphs)

"""
Sage defines circulant graphs without the cycle, whereas the paper defines it with the cycle
From:
Brimkov, Valentin. "Algorithmic and explicit determination of the Lovasz number for certain circulant graphs." Discrete Applied Mathematics 155.14 (2007): 1812-1825.
"""
c13_2 = graphs.CirculantGraph(13, 2)
c13_2.add_cycle(range(13))
c13_2.name(new = "c13_2")
add_to_lists(c13_2, graph_objects, all_graphs)

k3 = alpha_critical_easy[1]
k4 = alpha_critical_easy[2]

k10 = graphs.CompleteGraph(10)
k10.name(new="k10")
add_to_lists(k10, graph_objects, all_graphs)

# CE to independence_number(x) >= floor(tan(floor(gutman_energy(x))))
k37 = graphs.CompleteGraph(37)
k37.name(new = "k37")
add_to_lists(k37, graph_objects, counter_examples, all_graphs)

# Lipták, László, and László Lovász. "Critical facets of the stable set polytope." Combinatorica 21.1 (2001): 61-88.
k1_4 = graphs.CompleteBipartiteGraph(1, 4)
k1_4.name(new = "k1_4")
add_to_lists(k1_4, graph_objects, all_graphs)

# A 4 ray star with each ray subdivided into two edges
# Lipták, László, and László Lovász. "Critical facets of the stable set polytope." Combinatorica 21.1 (2001): 61-88.
k1_4_sub2 = Graph("[email protected]?^")
k1_4_sub2.name(new = "k1_4_sub2")
add_to_lists(k1_4_sub2, graph_objects, all_graphs)

# CE to independence_number(x) <= minimum(lovasz_theta(x), 2*e^sum_temperatures(x))
#   and to
# independence_number(x) <= minimum(floor(lovasz_theta(x)), 2*e^sum_temperatures(x))
#   and to
# independence_number(x) >= -brinkmann_steffen(x) + 1/2*card_center(x)
k1_9 = graphs.CompleteBipartiteGraph(1,9)
k1_9.name(new = "k1_9")
add_to_lists(k1_9, graph_objects, counter_examples, all_graphs)

# The line graph of k3,3
k3_3_line_graph = graphs.CompleteBipartiteGraph(3, 3).line_graph()
k3_3_line_graph.name(new = "k3_3 line graph")
add_to_lists(k3_3_line_graph, graph_objects, all_graphs)

k5_3=graphs.CompleteBipartiteGraph(5,3)
k5_3.name(new = "k5_3")
add_to_lists(k5_3, graph_objects, all_graphs)

# CE to independence_number(x) <= diameter^(max_degree-1)
# diameter is 16, Delta=3, alpha = 341
bt2_8 = graphs.BalancedTree(2,8)
bt2_8.name(new = "bt2_8")
add_to_lists(bt2_8, graph_objects, counter_examples, all_graphs)

#two c4's joined at a vertex
c4c4=graphs.CycleGraph(4)
for i in [4,5,6]:
    c4c4.add_vertex()
c4c4.add_edge(3,4)
c4c4.add_edge(5,4)
c4c4.add_edge(5,6)
c4c4.add_edge(6,3)
c4c4.name(new="c4c4")
add_to_lists(c4c4, graph_objects, all_graphs)

#two c5's joined at a vertex: eulerian, not perfect, not hamiltonian
c5c5=graphs.CycleGraph(5)
for i in [5,6,7,8]:
    c5c5.add_vertex()
c5c5.add_edge(0,5)
c5c5.add_edge(0,8)
c5c5.add_edge(6,5)
c5c5.add_edge(6,7)
c5c5.add_edge(7,8)
c5c5.name(new="c5c5")
add_to_lists(c5c5, graph_objects, all_graphs)

K4a=graphs.CompleteGraph(4)
K4b=graphs.CompleteGraph(4)
K4a.delete_edge(0,1)
K4b.delete_edge(0,1)
regular_non_trans = K4a.disjoint_union(K4b)
regular_non_trans.add_edge((0,0),(1,1))
regular_non_trans.add_edge((0,1),(1,0))
regular_non_trans.name(new="regular_non_trans")
add_to_lists(regular_non_trans, graph_objects, all_graphs)

c6ee = graphs.CycleGraph(6)
c6ee.add_edges([(1,5), (2,4)])
c6ee.name(new="c6ee")
add_to_lists(c6ee, graph_objects, all_graphs)

#c6ee plus another chord: hamiltonian, regular, vertex transitive
c6eee = copy(c6ee)
c6eee.add_edge(0,3)
c6eee.name(new="c6eee")
add_to_lists(c6eee, graph_objects, all_graphs)

#c8 plus one long vertical chord and 3 parallel horizontal chords
c8chorded = graphs.CycleGraph(8)
c8chorded.add_edge(0,4)
c8chorded.add_edge(1,7)
c8chorded.add_edge(2,6)
c8chorded.add_edge(3,5)
c8chorded.name(new="c8chorded")
add_to_lists(c8chorded, graph_objects, all_graphs)

#c8 plus 2 parallel chords: hamiltonian, tri-free, not vertex-transitive
c8chords = graphs.CycleGraph(8)
c8chords.add_edge(1,6)
c8chords.add_edge(2,5)
c8chords.name(new="c8chords")
add_to_lists(c8chords, graph_objects, all_graphs)

# C10 with an edge through the center
c10e = graphs.CycleGraph(10)
c10e.add_edge(0,5)
c10e.name(new = "c10e")
add_to_lists(c10e, graph_objects, all_graphs)

# C10e with another edge through center
c10ee = graphs.CycleGraph(10)
c10ee.add_edges([(0,5), (9, 4)])
c10ee.name(new = "c10ee")
add_to_lists(c10ee, graph_objects, all_graphs)

prismsub = graphs.CycleGraph(6)
prismsub.add_edge(0,2)
prismsub.add_edge(3,5)
prismsub.add_edge(1,4)
prismsub.subdivide_edge(1,4,1)
prismsub.name(new="prismsub")
add_to_lists(prismsub, graph_objects, all_graphs)

# ham, not vertex trans, tri-free, not cartesian product
prismy = graphs.CycleGraph(8)
prismy.add_edge(2,5)
prismy.add_edge(0,3)
prismy.add_edge(4,7)
prismy.name(new="prismy")
add_to_lists(prismy, graph_objects, all_graphs)

#c10 with chords, ham, tri-free, regular, planar, vertex transitive
sixfour = graphs.CycleGraph(10)
sixfour.add_edge(1,9)
sixfour.add_edge(0,2)
sixfour.add_edge(3,8)
sixfour.add_edge(4,6)
sixfour.add_edge(5,7)
sixfour.name(new="sixfour")
add_to_lists(sixfour, graph_objects, all_graphs)

#unique 24-vertex fullerene: hamiltonian, planar, not vertex transitive
fullerene_24 = Graph('[email protected]?PC?O`[email protected]@[email protected]??CC?G??GG?E???o??B???E???F')
fullerene_24.name(new="fullerene_24")
add_to_lists(fullerene_24, graph_objects, all_graphs)

#unique 26-atom fullerene: hamiltonian, planar, not vertex trans, radius=5, diam=6
fullerene_26 = Graph('[email protected]?PC?O`[email protected]@[email protected][email protected]_??K???W???W???H???E_')
fullerene_26.name(new="fullerene_26")
add_to_lists(fullerene_26, graph_objects, all_graphs)

#the unique 100-atom fullerene with minimum independence number of 43 (and IPR, tetrahedral symmetry)
fullerene_100 = Graph("[email protected]@@?OC?O`[email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected]????????[email protected][email protected][email protected]_????????????E????????[email protected]?????????????G??????????????OG???????????[email protected][email protected][email protected]_???????????????F")
fullerene_100.name(new="fullerene_100")
add_to_lists(fullerene_100, graph_objects, all_graphs)

"""
The Holton-McKay graph is the smallest planar cubic hamiltonian graph with an edge
that is not contained in a hamiltonian cycle. It has 24 vertices and the edges (0,3)
and (4,7) are not contained in a hamiltonian cycle. This graph was mentioned in
D. A. Holton and B. D. McKay, Cycles in 3-connected cubic planar graphs II, Ars
Combinatoria, 21A (1986) 107-114.

    sage: holton_mckay
    holton_mckay: Graph on 24 vertices
    sage: holton_mckay.is_planar()
    True
    sage: holton_mckay.is_regular()
    True
    sage: max(holton_mckay.degree())
    3
    sage: holton_mckay.is_hamiltonian()
    True
    sage: holton_mckay.radius()
    4
    sage: holton_mckay.diameter()
    6
"""
holton_mckay = Graph('WlCGKS??G?_D????_?g?DOa?C?O??G?CC?`?G??_?_?_??L')
holton_mckay.name(new="holton_mckay")
add_to_lists(holton_mckay, graph_objects, all_graphs)

#an example of a bipartite, 1-tough, not van_den_heuvel, not hamiltonian graph
kratsch_lehel_muller = graphs.PathGraph(12)
kratsch_lehel_muller.add_edge(0,5)
kratsch_lehel_muller.add_edge(6,11)
kratsch_lehel_muller.add_edge(4,9)
kratsch_lehel_muller.add_edge(1,10)
kratsch_lehel_muller.add_edge(2,7)
kratsch_lehel_muller.name(new="kratsch_lehel_muller")
add_to_lists(kratsch_lehel_muller, graph_objects, all_graphs)

#ham, not planar, not anti_tutte
c6xc6 = graphs.CycleGraph(6).cartesian_product(graphs.CycleGraph(6))
c6xc6.name(new="c6xc6")
add_to_lists(c6xc6, graph_objects, all_graphs)

c7xc7 = graphs.CycleGraph(7).cartesian_product(graphs.CycleGraph(7))
c7xc7.name(new="c7xc7")
add_to_lists(c7xc7, graph_objects, all_graphs)

# Product Graphs, fig. 1.13
c6xk2 = graphs.CycleGraph(6).cartesian_product(graphs.CompleteGraph(2))
c6xk2.name(new = "c6xk2")
add_to_lists(c6xk2, graph_objects, all_graphs)

# Product Graphs, fig. 1.13
k1_4xp3 = graphs.CompleteBipartiteGraph(1, 4).cartesian_product(graphs.PathGraph(3))
k1_4xp3.name(new = "k1_4xp3")
add_to_lists(k1_4xp3, graph_objects, all_graphs)

# Product Graphs, fig. 1.14
p4xk3xk2 = graphs.PathGraph(4).cartesian_product(graphs.CompleteGraph(3)).cartesian_product(graphs.CompleteGraph(2))
p4xk3xk2.name(new = "p4xk3xk2")
add_to_lists(p4xk3xk2, graph_objects, all_graphs)

# Product Graphs, fig. 4.1
p3xk2xk2 = graphs.PathGraph(3).cartesian_product(graphs.CompleteGraph(2)).cartesian_product(graphs.CompleteGraph(2))
p3xk2xk2.name(new = "p3xk2xk2")
add_to_lists(p3xk2xk2, graph_objects, all_graphs)

# Product Graphs, fig. 5.1
p4Xp5 = graphs.PathGraph(4).strong_product(graphs.PathGraph(5))
p4Xp5.name(new = "p4Xp5")
add_to_lists(p4Xp5, graph_objects, all_graphs)

# Product Graphs, Fig 6.1
k3lxp3 = graphs.CompleteGraph(3).lexicographic_product(graphs.PathGraph(3))
k3lxp3.name(new = "k3lxp3")
add_to_lists(k3lxp3, graph_objects, all_graphs)

# Product Graphs, Fig 6.1
p3lxk3 = graphs.PathGraph(3).lexicographic_product(graphs.CompleteGraph(3))
p3lxk3.name(new = "p3lxk3")
add_to_lists(p3lxk3, graph_objects, all_graphs)

"""
Referenced p.15
Mathew, K. Ashik, and Patric RJ Östergård. "New lower bounds for the Shannon capacity of odd cycles." Designs, Codes and Cryptography (2015): 1-10.
"""
c5Xc5 = graphs.CycleGraph(5).strong_product(graphs.CycleGraph(5))
c5Xc5.name(new = "c5Xc5")
add_to_lists(c5Xc5, graph_objects, all_graphs)

#non-ham, 2-connected, eulerian (4-regular)
gould = Graph('[email protected]')
gould.name(new="gould")
add_to_lists(gould, graph_objects, all_graphs)

#two k5s with single edge removed from each and lines joining these 4 points to a new center point, non-hamiltonian
throwing = Graph('J~wWGGB?wF_')
throwing.name(new="throwing")
add_to_lists(throwing, graph_objects, all_graphs)

#k4 plus k2 on one side, open k5 on other, meet at single point in center, non-hamiltonian
throwing2 = Graph("K~wWGKA?gB_N")
throwing2.name(new="throwing2")
add_to_lists(throwing2, graph_objects, all_graphs)

#similar to throwing2 with pair of edges swapped, non-hamiltonian
throwing3 = Graph("K~wWGGB?oD_N")
throwing3.name(new="throwing3")
add_to_lists(throwing3, graph_objects, all_graphs)

#graph has diameter != radius but is hamiltonian
tent = graphs.CycleGraph(4).join(Graph(1),labels="integers")
tent.name(new="tent")
add_to_lists(tent, graph_objects, all_graphs)

# C5 with chords from one vertex to other 2 (showed up in auto search for CE's): hamiltonian
bridge = Graph("DU{")
bridge.name(new="bridge")
add_to_lists(bridge, graph_objects, all_graphs)

# nico found the smallest hamiltonian overfull graph
non_ham_over = Graph("HCQRRQo")
non_ham_over.name(new="non_ham_over")
add_to_lists(non_ham_over, graph_objects, all_graphs)

# From Ryan Pepper
ryan = Graph("[email protected]?OC?AW???O?C??B???G?A?_??R")
ryan.name(new="ryan")
add_to_lists(ryan, graph_objects, all_graphs)

# Ryan Pepper
# CE to independence_number(x) <= 2 * x.chromatic_number() + 2 * residue(x)
# has alpha=25,chi=2,residue=10
ryan2=graphs.CirculantGraph(50,[1,3])
ryan2.name(new="circulant_50_1_3")
add_to_lists(ryan2, graph_objects, counter_examples, all_graphs)

# From Ryan Pepper
# CE to independence_number(x) >= diameter(x) - 1 for regular graphs
pepper_1_gadget = Graph('Ot???CA?WB`[email protected]_B_B?A')
pepper_1_gadget.name(new = "pepper_1_gadget")
add_to_lists(pepper_1_gadget, graph_objects, counter_examples, all_graphs)

# p10 joined to 2 points of k4
# CE to chromatic_number <= avg_degree + 1
p10k4=Graph('[email protected][email protected]_B?B_')
p10k4.name(new="p10k4")
add_to_lists(p10k4, graph_objects, counter_examples, all_graphs)

# star on 13 points with added edge:
# CE to independence_number(x) <= dom + girth(x)^2
s13e = Graph('M{aCCA?_C?O?_?_??')
s13e.name(new="s13e")
add_to_lists(s13e, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= 2 * girth(x)^2 + 2
# Star with 22 rays plus extra edge
s22e = graphs.StarGraph(22)
s22e.add_edge(1,2)
s22e.name(new="s22e")
add_to_lists(s22e, graph_objects, counter_examples, all_graphs)

# Graph from delavina's jets paper
starfish = Graph('N~~eeQoiCoM?Y?U?F??')
starfish.name(new="starfish")
add_to_lists(starfish, graph_objects, all_graphs)

# difficult graph from INP: order=11, alpha=4, best lower bound < 3
difficult11 = Graph('J?`FBo{fdb?')
difficult11.name(new="difficult11")
add_to_lists(difficult11, graph_objects, all_graphs)

# c4 joined to K# at point: not KE, alpha=theta=nu=3, delting any vertex gives KE graph
c5k3=Graph('FheCG')
c5k3.name(new="c5k3")
add_to_lists(c5k3, graph_objects, all_graphs)

# mycielskian of a triangle:
# CE to chi <= max(clique, nu)
# chi=4, nu = clique = 3
c3mycielski = Graph('FJnV?')
c3mycielski.name(new="c3mycieski")
add_to_lists(c3mycielski, problem_graphs , counter_examples, all_graphs)

# 4th mycielskian of a triangle,
# CE to chi <= clique + girth
# chi = 7, clique = girth = 3
c3mycielski4 = Graph('[email protected]@[email protected]?NyB`qLepJTgRXkAkU?JPg?VB_?W[[email protected]???Bs???Bw???A??F~~_B}?^sB`o[MOuZErWatYUjObXkZL_QpWUJ?CsYEbO?fB_w[?A`[email protected]???Ds?M_???V_?{????oB}?????o[M?????WuZ?????EUjO?????rXk?????BUJ??????EsY??????Ew[??????B`o???????xk???????FU_???????\\k????????|_????????}_????????^_?????????')
c3mycielski4.name(new="c3mycielski4")
add_to_lists(c3mycielski4, graph_objects, counter_examples, all_graphs)

# A PAW is a traingle with a pendant
# Shows up in a sufficient condition for hamiltonicity
paw=Graph('C{')
paw.name(new="paw")
add_to_lists(paw, graph_objects, all_graphs)

# 2 octahedrons, remove one edge from each, add vertex, connect it to deleted edge vertices
# its regular of degree 4
binary_octahedron = Graph('L]lw??B?oD_Noo')
binary_octahedron.name(new = "binary_octahedron")
add_to_lists(binary_octahedron, graph_objects, all_graphs)

# this graph shows that the cartesian product of 2 KE graphs is not necessarily KE
# appears in Abay-Asmerom, Ghidewon, et al. "Notes on the independence number in the Cartesian product of graphs." Discussiones Mathematicae Graph Theory 31.1 (2011): 25-35.
paw_x_paw = paw.cartesian_product(paw)
paw_x_paw.name(new = "paw_x_paw")
add_to_lists(paw_x_paw, graph_objects, all_graphs)

#a DART is a kite with a pendant
dart = Graph('DnC')
dart.name(new="dart")
add_to_lists(dart, graph_objects, all_graphs)

# CE to ((is_chordal)^(is_forest))->(has_residue_equals_alpha)
ce2=Graph("HdGkCA?")
ce2.name(new = "ce2")
add_to_lists(ce2, graph_objects, counter_examples, all_graphs)

# CE to ((~(is_planar))&(is_chordal))->(has_residue_equals_alpha)
ce4=Graph("G~sNp?")
ce4.name(new = "ce4")
add_to_lists(ce4, graph_objects, counter_examples, all_graphs)

# CE to (((is_line_graph)&(is_cartesian_product))|(is_split))->(has_residue_equals_alpha)
ce5=Graph("X~}AHKVB{GGPGRCJ`B{GOO`C`AW`AwO`}CGOO`AHACHaCGVACG^")
ce5.name(new = "ce5")
add_to_lists(ce5, graph_objects, counter_examples, all_graphs)

# CE to (is_split)->((order_leq_twice_max_degree)&(is_chordal))
ce6 = Graph("[email protected]")
ce6.name(new = "ce6")
add_to_lists(ce6, graph_objects, counter_examples, all_graphs)

# CE to (has_residue_equals_alpha)->((is_bipartite)->(order_leq_twice_max_degree))
ce7 = Graph("FpGK?")
ce7.name(new = "ce7")
add_to_lists(ce7, graph_objects, counter_examples, all_graphs)

# CE to ((has_paw)&(is_circular_planar))->(has_residue_equals_alpha)
ce8 = Graph('[email protected]_G')
ce8.name(new = "ce8")
add_to_lists(ce8, graph_objects, counter_examples, all_graphs)

# CE to ((has_H)&(is_forest))->(has_residue_equals_alpha)
ce9 = Graph('IhCGGD?G?')
ce9.name(new = "ce9")
add_to_lists(ce9, graph_objects, counter_examples, all_graphs)

# CE to (((is_eulerian)&(is_planar))&(has_paw))->(has_residue_equals_alpha)
ce10=Graph('[email protected][email protected]')
ce10.name(new = "ce10")
add_to_lists(ce10, graph_objects, counter_examples, all_graphs)

# CE to (((is_cubic)&(is_triangle_free))&(is_H_free))->(has_residue_equals_two)
ce12 = Graph("Edo_")
ce12.name(new = "ce12")
add_to_lists(ce12, graph_objects, counter_examples, all_graphs)

# CE to ((diameter_equals_twice_radius)&(is_claw_free))->(has_residue_equals_two)
ce13 = Graph("ExOG")
ce13.name(new = "ce13")
add_to_lists(ce13, graph_objects, counter_examples, all_graphs)

# CE to (~(matching_covered))->(has_residue_equals_alpha)
ce14 = Graph('[email protected]?')
ce14.name(new = "[email protected]?")
add_to_lists(ce14, graph_objects, counter_examples, all_graphs)

"""
CE to independence_number(x) <= 10^order_automorphism_group(x)

    sage: order(ce15)
    57
    sage: independence_number(ce15)
    25
"""
ce15 = Graph("[email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected]??????MCOC???O_??[[email protected][email protected][email protected][email protected]_???`[email protected][email protected][email protected][email protected][email protected][email protected]`??")
ce15.name(new = "ce15")
add_to_lists(ce15, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= 2*maximum(welsh_powell(x), max_even_minus_even_horizontal(x))
ce16 = Graph("[email protected][email protected][email protected][email protected][email protected][email protected][email protected]@@??O?OC[email protected][email protected]@?pY?G?")
ce16.name(new = "ce16")
add_to_lists(ce16, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= 1/2*cvetkovic(x)
ce17 = Graph("[email protected]@[email protected]?C?S")
ce17.name(new = "ce17")
add_to_lists(ce17, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= matching_number - sigma_dist2
ce18 = Graph("[email protected][email protected][email protected][email protected]???CI?S?OGG?ACgQa_Cw^[email protected]?Gh??ogD_??dR[?AG?")
ce18.name(new = "ce18")
add_to_lists(ce18, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(max_even_minus_even_horizontal(x), radius(x)*welsh_powell(x))
ce19 = Graph('[email protected]{_')
ce19.name(new = "ce19")
add_to_lists(ce19, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= card_center(x) + max_even_minus_even_horizontal(x) + 1
ce20 = Graph('M?CO?k?OWEQO_O]c_')
ce20.name(new = "ce20")
add_to_lists(ce20, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= median_degree(x)^2 + card_periphery(x)
ce21 = Graph('FiQ?_')
ce21.name(new = "ce21")
add_to_lists(ce21, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= brinkmann_steffen(x) + max_even_minus_even_horizontal(x) + 1
ce22 = Graph('[email protected]?OO?GD?')
ce22.name(new = "ce22")
add_to_lists(ce22, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= inverse_degree(x) + order_automorphism_group(x) + 1
ce23 = Graph("HkIU|eA")
ce23.name(new = "ce23")
add_to_lists(ce23, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= ceil(eulerian_faces(x)/diameter(x)) +max_even_minus_even_horizontal(x)
ce24 = Graph('[email protected]@AG?')
ce24.name(new = "ce24")
add_to_lists(ce24, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= floor(e^(maximum(max_even_minus_even_horizontal(x), fiedler(x))))
ce25 = Graph('[email protected]')
ce25.name(new = "ce25")
add_to_lists(ce25, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(card_periphery(x), radius(x)*welsh_powell(x))
ce26 = Graph("[email protected]?Oa?BC_?OOaO")
ce26.name(new = "ce26")
add_to_lists(ce26, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= floor(average_distance(x)) + maximum(max_even_minus_even_horizontal(x), brinkmann_steffen(x))
ce27 = Graph("K_GBXS`ysCE_")
ce27.name(new = "ce27")
add_to_lists(ce27, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= minimum(annihilation_number(x), 2*e^sum_temperatures(x))
ce28 = Graph("g??O?C_?`[email protected][email protected][email protected]????????_???GHC???CG?[email protected]??_??OB?C?_??????_???G???C?O?????O??A??????G??")
ce28.name(new = "ce28")
add_to_lists(ce28, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(2*welsh_powell(x), maximum(max_even_minus_even_horizontal(x), laplacian_energy(x)))
ce29 = Graph("[email protected][email protected]@[email protected]")
ce29.name(new = "ce29")
add_to_lists(ce29, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(order_automorphism_group(x), 2*cvetkovic(x) - matching_number(x))
ce30 = Graph("G~q|{W")
ce30.name(new = "ce30")
add_to_lists(ce30, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= max_even_minus_even_horizontal(x) + min_degree(x) + welsh_powell(x)
ce31 = Graph("[email protected]?POAi?")
ce31.name(new = "ce31")
add_to_lists(ce31, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= order(x)/szekeres_wilf(x)
ce32 = Graph('H?`@Cbg')
ce32.name(new = "ce32")
add_to_lists(ce32, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= max_even_minus_even_horizontal(x) + minimum(card_positive_eigenvalues(x), card_center(x) + 1)
ce33 = Graph("O_aHgP_kVSGOCXAiODcA_")
ce33.name(new = "ce33")
add_to_lists(ce33, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= card_center(x) + maximum(diameter(x), card_periphery(x))
ce34 = Graph('H?PA_F_')
ce34.name(new = "ce34")
add_to_lists(ce34, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= card_center(x) + maximum(diameter(x), card_periphery(x))ce35 = Graph("")
ce35 = Graph("HD`cgGO")
ce35.name(new = "ce35")
add_to_lists(ce35, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= max_degree(x) - order_automorphism_group(x)
ce36 = Graph('ETzw')
ce36.name(new = "ce36")
add_to_lists(ce36, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(card_center(x), diameter(x)*max_degree(x))
ce37 = Graph("[email protected]@[email protected][email protected][email protected]???O?????????????C???????_???????C?_?W???C????????_?????????????[email protected][email protected][email protected]_??????_??G???K??????A????C??????????A???_?A????`[email protected][email protected]_G??C???[email protected][email protected]???O??????CC???O?????????OC_??[email protected][email protected][email protected]@???????C???[email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected]?A_????????CA????????????????H???????????????????O????_??OG??Ec?????O??A??_???_???O?C??`[email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected]???O????_`[email protected][email protected]?G?A????O??G???_????_?????A?G_?C?????????C?")
ce37.name(new = "ce37")
add_to_lists(ce37, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= abs(-card_center(x) + min_degree(x)) + max_even_minus_even_horizontal(x)
ce38 = Graph('FVS_O')
ce38.name(new = "ce38")
add_to_lists(ce38, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= abs(-card_center(x) + max_degree(x)) + max_even_minus_even_horizontal(x)
ce39 = Graph("FBAuo")
ce39.name(new = "ce39")
add_to_lists(ce39, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= floor(inverse_degree(x)) + order_automorphism_group(x) + 1
ce40 = Graph('Htji~Ei')
ce40.name(new = "ce40")
add_to_lists(ce40, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= card_center(x) + maximum(residue(x), card_periphery(x))
ce42 = Graph('GP[KGC')
ce42.name(new = "ce42")
add_to_lists(ce42, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(girth(x), (barrus_bound(x) - order_automorphism_group(x))^2)
ce43 = Graph("Exi?")
ce43.name(new = "ce43")
add_to_lists(ce43, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= (brinkmann_steffen(x) - szekeres_wilf(x))^2 + max_even_minus_even_horizontal(x)
ce44 = Graph('GGDSsg')
ce44.name(new = "ce44")
add_to_lists(ce44, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(max_even_minus_even_horizontal(x), radius(x)*szekeres_wilf(x))
ce45 = Graph("FWKH?")
ce45.name(new = "ce45")
add_to_lists(ce45, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(card_periphery(x), radius(x)*szekeres_wilf(x))
ce46 = Graph('F`I`?')
ce46.name(new = "ce46")
add_to_lists(ce46, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(card_periphery(x), diameter(x) + inverse_degree(x))
ce47 = Graph("KVOzWAxewcaE")
ce47.name(new = "ce47")
add_to_lists(ce47, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(card_periphery(x), max_even_minus_even_horizontal(x) + min_degree(x))
ce48 = Graph('Iq][email protected]_s?')
ce48.name(new = "ce48")
add_to_lists(ce48, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= sqrt(card_positive_eigenvalues(x))
ce49 = Graph("K^~lmrvv{~~Z")
ce49.name(new = "ce49")
add_to_lists(ce49, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= max_degree(x) + maximum(max_even_minus_even_horizontal(x), sigma_dist2(x))
ce50 = Graph('[email protected][email protected]@@m?a?WPWI?G_A_?C`[email protected]_G?GDI]CYG??GA_A??')
ce50.name(new = "ce50")
add_to_lists(ce50, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= matching_number(x) - order_automorphism_group(x) - 1
ce51 = Graph("Ivq~j^~vw")
ce51.name(new = "ce51")
add_to_lists(ce51, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= order(x)/szekeres_wilf(x)
ce52 = Graph('H?QaOiG')
ce52.name(new = "ce52")
add_to_lists(ce52, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= matching_number(x) - sigma_dist2(x) - 1
ce53 = Graph("]?GEPCGg]S?`@[email protected][email protected]_gm?GW_og?pWO?_??GQ?A?^HIRwH?Y?__BC?G?[[email protected][O?GW")
ce53.name(new = "ce53")
add_to_lists(ce53, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= -average_distance(x) + ceil(lovasz_theta(x))
ce54 = Graph('lckMIWzcWDsSQ_xTlFX?AoCbEC?f^xwGHOA_q?m`PDDvicEWP`[email protected]``[email protected]}`CiG?HCsm_JO?QhI`?ARLAcdBAaOh_QMG?`D_o_FvQgHGHD?sKLEAR^[email protected][email protected]`DkC')
ce54.name(new = "ce54")
add_to_lists(ce54, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= -card_periphery(x) + matching_number(x)
ce55 = Graph("I~~~~~~zw")
ce55.name(new = "ce55")
add_to_lists(ce55, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= lovasz_theta(x)/edge_con(x)
ce56 = Graph('HsaGpOe')
ce56.name(new = "ce56")
add_to_lists(ce56, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= minimum(max_degree(x), floor(lovasz_theta(x)))
ce57 = Graph("^?H{BDHqHosG??OkHOhE??B[[email protected]_A?CoA^[email protected][email protected][email protected]_?_sGcED`@``O")
ce57.name(new = "ce57")
add_to_lists(ce57, graph_objects, counter_examples, all_graphs)

# CE to independence_number>= barrus_bound(x) - max(card_center(x), card_positive_eigenvalues(x))
ce58 = Graph('Sj[{Eb~on~nls~NJWLVz~~^|{l]b\uFss')
ce58.name(new = "ce58")
add_to_lists(ce58, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= floor(tan(barrus_bound(x) - 1))
ce59 = Graph("[email protected]??_?N??F??B_??w?")
ce59.name(new = "ce59")
add_to_lists(ce59, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= -1/2*diameter(x) + lovasz_theta(x)
ce60 = Graph('wSh[?GCfclJm?hmgA^We?Q_KIXbf\@SgDNxpwHTQIsIB?MIDZukArBAeXE`vqDLbHCwf{fD?bKSVLklQHspD`[email protected]?yW\YOCeaqmOfsZ?rmOSM?}HwPCIAYLdFx?o[B?]ZYb~IK~Z`ol~Ux[B]tYUE`_gnVyHRQ?{cXG?k\[email protected]?Q?Qb`SKM`@[BVCKDcMxF|ADGGMBW`ANV_IKw??DRkY\KOCW??P_?ExJDSAg')
ce60.name(new = "ce60")
add_to_lists(ce60, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(card_negative_eigenvalues(x), max_common_neighbors(x) + max_even_minus_even_horizontal(x))
ce61 = Graph("KsaAA?OOC??C")
ce61.name(new = "ce61")
add_to_lists(ce61, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= minimum(floor(lovasz_theta(x)), tan(spanning_trees_count(x)))
ce62 = Graph("qWGh???BLQcAH`[email protected][email protected]@WOEBgRC`oSE`[email protected][[email protected][email protected]?__G}ScHO{[email protected]?C[[email protected][email protected][email protected][email protected]_OBbHGOl??\[email protected]?E`[email protected]`GaCgC?JjQ???AGJgDJAGsdcqEA_a_q?")
ce62.name(new = "ce62")
add_to_lists(ce62, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= diameter(x)/different_degrees(x)
ce63 = Graph("[email protected]")
ce63.name(new = "ce63")
add_to_lists(ce63, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= -max_common_neighbors(x) + min_degree(x)
ce64 = Graph('`szvym|h~RMQLTNNiZzsgQynDR\p~~rTZXi~n`kVvKolVJfP}TVEN}Thj~tv^KJ}D~VqqsNy|NY|ybklZLnz~TfyG')
ce64.name(new = "ce64")
add_to_lists(ce64, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= -10^different_degrees(x) + matching_number(x)
ce65 = Graph("W~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")
ce65.name(new = "ce65")
add_to_lists(ce65, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= girth^max_degree+1
ce66 = Graph("[email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected]@[email protected]????????C??C?????G??")
ce66.name(new = "ce66")
add_to_lists(ce66, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(cycle_space_dimension(x), floor(lovasz_theta(x)))
ce67 = Graph("G??EDw")
ce67.name(new = "ce67")
add_to_lists(ce67, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= minimum(card_positive_eigenvalues(x), 2*card_zero_eigenvalues(x))
ce68 = Graph('HzzP|~]')
ce68.name(new = "ce68")
add_to_lists(ce68, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(max_degree(x), radius(x)^card_periphery(x))
ce69 = Graph("F?BvO")
ce69.name(new = "ce69")
add_to_lists(ce69, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= floor(lovasz_theta(x))/vertex_con(x)
ce70 = Graph('[email protected]??????O?M??`S??A?`[email protected]????`[email protected][email protected]@[email protected]_??G??A?`[email protected][email protected][email protected][email protected][email protected][email protected][email protected]?Ao?????C???A??????_??SG??cOC?[email protected]???[email protected][email protected][email protected]@[email protected][email protected][email protected]??`[email protected][email protected][email protected]@[email protected]@[email protected][email protected][email protected][email protected][email protected][email protected][email protected]@??????????A_??????')
ce70.name(new = "ce70")
add_to_lists(ce70, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(matching_number(x), critical_independence_number(x))
ce71 = Graph('ECYW')
ce71.name(new = "ce71")
add_to_lists(ce71, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x)>=-1/2*x.diameter() + x.lovasz_theta()
ce72 = Graph('fdSYkICGVs_m_TPs`Fmj_|[email protected]@_[@[email protected]`TC{[email protected]?HBDS[R?CdG\[email protected]?G`NHGXgYpVGCoJdOKBJQAsG|ICE_BeMQGOwKqSd\W?CRg')
ce72.name(new = "ce72")
add_to_lists(ce72, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= minimum(floor(lovasz_theta(x)), max_even_minus_even_horizontal(x) + 1)
ce73 = Graph('[email protected][email protected][email protected][email protected][email protected][email protected]_?_G_GC_??E?O?O`[email protected][email protected][email protected][email protected]??')
ce73.name(new = "ce73")
add_to_lists(ce73, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= minimum(diameter(x), lovasz_theta(x))
ce74 = Graph("FCQb_")
ce74.name(new = "ce74")
add_to_lists(ce74, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= minimum(girth(x), floor(lovasz_theta(x)))
ce75 = Graph('E?Bw')
ce75.name(new = "ce75")
add_to_lists(ce75, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(average_distance(x), max_even_minus_even_horizontal(x))*sum_temperatures(x)
ce76 = Graph("[email protected][email protected][email protected][email protected][email protected]`[email protected]??XA???AS???oE`[email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected][email protected]@[email protected][email protected][email protected]?K?_O_CG??A?")
ce76.name(new = "ce76")
add_to_lists(ce76, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(matching_number(x), critical_independence_number(x))
ce77 = Graph("iF\ZccMAoW`[email protected][email protected]@_??_[email protected][email protected][email protected]?_??S???O??")
ce77.name(new = "ce77")
add_to_lists(ce77, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(max_degree(x), radius(x)^card_periphery(x))
ce78 = Graph("G_aCp[")
ce78.name(new = "ce78")
add_to_lists(ce78, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= residue(x)^2
ce79 = Graph('J?B|~fpwsw_')
ce79.name(new = "ce79")
add_to_lists(ce79, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= 10^(card_center(x)*log(10)/log(sigma_dist2(x)))
ce80 = Graph('T?????????????????F~~~v}~|zn}ztn}zt^')
ce80.name(new = "ce80")
add_to_lists(ce80, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= diameter(x)^card_periphery(x)
ce81 = Graph('P?????????^~v~V~rzyZ~du{')
ce81.name(new = "ce81")
add_to_lists(ce81, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= radius(x)*residue(x) + girth(x)
ce82 = Graph('O????B~~^Zx^wnc~ENqxY')
ce82.name(new = "ce82")
add_to_lists(ce82, graph_objects, counter_examples, all_graphs)

"""
CE to independence_number(x) <= minimum(lovasz_theta(x), residue(x)^2)
    and
    <= minimum(annihilation_number(x), residue(x)^2)
    and
    <= minimum(fractional_alpha(x), residue(x)^2)
    and
    <= minimum(cvetkovic(x), residue(x)^2)
    and
    <= minimum(residue(x)^2, floor(lovasz_theta(x)))
    and
    <= minimum(size(x), residue(x)^2)
"""
ce83 = Graph('LEYSrG|mrQ[ppi')
ce83.name(new = "ce83")
add_to_lists(ce83, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(laplacian_energy(x), brinkmann_steffen(x)^2)
ce84 = Graph('[email protected][email protected][email protected][email protected][email protected]?S?O??[email protected]