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):
    """
    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.

    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)
    count = 0
    alpha_critical_name_list = []
    for g in graphgen:
        if g.is_connected():
            count += 1
            if is_alpha_critical(g):
                alpha_critical_name_list.append(g.graph6_string())
    s = "alpha_critical_name_list_{}".format(order)
    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):
    n = g.order()

    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()
    V = g.vertices()
    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 i in [1..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([len_v..len_v+3])
        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 A[u][v] == 1 and A[u][w] == 1 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..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..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


#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 = []

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 median(g.degree())
add_to_lists(median_degree, efficient_invariants, all_invariants)

def inverse_degree(g):
    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.

        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.

        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):
    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):
    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):
    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], min=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):
    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):
    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())
    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
    n=g.order()
    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)

def vertex_con(g):
    return g.vertex_connectivity()
add_to_lists(vertex_con, efficient_invariants, all_invariants)

def edge_con(g):
    return g.edge_connectivity()
add_to_lists(edge_con, 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 [1..(g.order()-1)]:
            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 edge in g.edges(labels = false):
        sum += (2 / (g.degree()[edge[0]] + g.degree()[edge[1]]))
    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
    """
    if edge == None:
        edge_clusering_centralities = []
        for e in g.edges(labels = False):
            sum = 0
            for v in g.vertices():
                if g.subgraph(g.neighbors(v) + [v]).has_edge(e):
                    sum += 1
            edge_clusering_centralities.append(sum)
        return edge_clusering_centralities
    else:
        for v in g.vertices():
            sum = 0
            if g.subgraph(g.neighbors(v) + [v]).has_edge(edge):
                sum += 1
        return sum

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.spectrum()
    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)

sage_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.clustering_average, Graph.spanning_trees_count]

for i in sage_invariants:
    add_to_lists(i, 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 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 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)

#####
# 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 chromatic_index(g):
    if g.size() == 0:
        return 0
    import sage.graphs.graph_coloring
    return sage.graphs.graph_coloring.edge_coloring(g, value_only=True)
add_to_lists(chromatic_index, intractable_invariants, all_invariants)

def chromatic_num(g):
    return g.chromatic_number()
add_to_lists(chromatic_num, 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 [1..upper]:
        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)

add_to_lists(Graph.treewidth, intractable_invariants, all_invariants)
add_to_lists(Graph.clique_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):
    """
    tests if graph has vertex adjacent to all others, also known as "universal vertex"
        sage: has_star_center(flower_with_3_petals)
        True
        sage: has_star_center(c4)
        False
    """
    n = g.order()
    return max_degree(g) == (n-1)


#split graphs have the property that their complements are chordal
def is_complement_of_chordal(g):
    """
    tests is a graph is a complement of a chordal graph
        sage: is_complement_of_chordal(p4)
        True
        sage: is_complement_of_chordal(p5)
        False
    """
    h = g.complement()
    return h.is_chordal()

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

    Related to the Friendship Theorem: the only connected graphs where every pair of vertices
    has a unique neighbor are flowers.

    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
    """
    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):
    """
    True if all a,b,u,v satisfy dist(a,b) = dist(u,v) => there is an automorphism sending a->u and b->v

    sage: is_distance_transitive(graphs.Tutte12Cage())
    False
    sage: is_distance_transitive(graphs.FosterGraph())
    True
    """
    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):
            if dist_dict[u].get(v, +Infinity) == d: # By default, no entry if disconnected. We substitute +Infinity.
                sameDistPairs.append(Set([u,v]))
        if len(sameDistPairs) >= 2:
            if not(len(sameDistPairs) == len(auto_group.orbit(sameDistPairs[0], action = "OnSets"))):
                return False
    return True

#sufficient condition for hamiltonicity
def is_dirac(g):
    n = g.order()
    deg = g.degree()
    delta=min(deg)
    if n/2 <= delta and n > 2:
        return True
    else:
        return False

#sufficient condition for hamiltonicity
def is_ore(g):
    A = g.adjacency_matrix()
    n = g.order()
    D = g.degree()
    for i in range(n):
        for j in range(i):
            if A[i][j]==0:
                if D[i] + D[j] < n:
                    return False
    return True

#sufficient condition for hamiltonicity
def is_haggkvist_nicoghossian(g):
    k = vertex_con(g)
    n = g.order()
    delta = min(g.degree())
    if k >= 2 and delta >= (1.0/3)*(n+k):
        return True
    else:
        return False

#sufficient condition for hamiltonicity
def is_genghua_fan(g):
    k = vertex_con(g)
    if k < 2:
        return False
    D = g.degree()
    Dist = g.distance_all_pairs()
    V = g.vertices()
    n = g.order()
    for i in range(n):
        for j in range (i):
            if Dist[V[i]][V[j]]==2 and max(D[i],D[j]) < n/2.0:
                return False
    return True

#sufficient condition for hamiltonicity
def is_planar_transitive(g):
    if g.order() > 2 and g.is_planar() and g.is_vertex_transitive():
        return True
    else:
        return False

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

#sufficient condition for hamiltonicity
def is_generalized_dirac(g):
    n = g.order()
    k = vertex_con(g)
    if k < 2:
        return False
    for p in Subsets(g.vertices(),2):
        if g.is_independent_set(p):
            if len(neighbors_set(g,p)) < (2.0*n-1)/3:
                return False
    return True

#necessary condition for hamiltonicity
def is_van_den_heuvel(g):
    n = g.order()
    lc = sorted(graphs.CycleGraph(n).laplacian_matrix().eigenvalues())
    lg = sorted(g.laplacian_matrix().eigenvalues())

    for lci, lgi in zip(lc, lg):
        if lci > lgi:
            return False

    def Q(g):
        A = g.adjacency_matrix()

        D = A.parent(0)

        if A.is_sparse():
            row_sums = {}
            for (i,j), entry in A.dict().iteritems():
                row_sums[i] = row_sums.get(i, 0) + entry
            for i in range(A.nrows()):
                D[i,i] += row_sums.get(i, 0)
        else:
            row_sums=[sum(v) for v in A.rows()]
            for i in range(A.nrows()):
                D[i,i] += row_sums[i]

        return D + A

    qc = sorted(Q(graphs.CycleGraph(n)).eigenvalues())
    qg = sorted(Q(g).eigenvalues())

    for qci, qgi in zip(qc, qg):
        if qci > qgi:
            return False

    return True

#necessary condition for hamiltonicity
def is_two_connected(g):
    """
    Returns True if the graph is 2-connected and False otherwise. A graph is
    2-connected if the removal of any single vertex gives a connected graph.
    By definition a graph on 2 or less vertices is not 2-connected.

        sage: is_two_connected(graphs.CycleGraph(5))
        True
        sage: is_two_connected(graphs.PathGraph(5))
        False
        sage: is_two_connected(graphs.CompleteGraph(2))
        False
        sage: is_two_connected(graphs.CompleteGraph(1))
        False
    """
    if g.order() <= 2:
        return False
    from itertools import combinations
    for s in combinations(g.vertices(), g.order() - 1):
        if not g.subgraph(s).is_connected():
            return False
    return True

#part of pebbling class0 sufficient condition
def is_three_connected(g):
    """
    Returns True if the graph is 3-connected and False otherwise. A graph is
    3-connected if the removal of any single vertex or any pair of vertices
    gives a connected graph. By definition a graph on 3 or less vertices is
    not 3-connected.

        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(graphs.CompleteGraph(1))
        False
    """
    if g.order() <= 3:
        return False
    from itertools import combinations
    for s in combinations(g.vertices(), g.order() - 2):
        if not g.subgraph(s).is_connected():
            return False
    return True

def is_four_connected(g):
    """
    True if g is at least four connected, i.e. must remove at least 4 vertices to disconnect graph

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

#sufficient condition for hamiltonicity
def is_lindquester(g):
    k = vertex_con(g)
    if k < 2:
        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):
    n = g.order()
    e = g.size()
    if not g.has_multiple_edges():
        return e == n*(n-1)/2

    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):
    return g.subgraph_search(c4, induced=True) is not None

def is_c4_free(g):
    return not has_c4(g)

def has_paw(g):
    return g.subgraph_search(paw, induced=True) is not None

def is_paw_free(g):
    return not has_paw(g)

def has_dart(g):
    return g.subgraph_search(dart, induced=True) is not None

def is_dart_free(g):
    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):
    return g.subgraph_search(p4, induced=True) is not None

def has_kite(g):
    return g.subgraph_search(kite_with_tail, induced=True) is not None

def is_kite_free(g):
    return not has_kite(g)

def has_claw(g):
    return g.subgraph_search(graphs.ClawGraph(), induced=True) is not None

def is_claw_free(g):
    return not has_claw(g)

def has_H(g):
    return g.subgraph_search(double_fork, induced=True) is not None

def is_H_free(g):
    return not has_H(g)

def has_fork(g):
    return g.subgraph_search(fork, induced=True) is not None

def is_fork_free(g):
    return not has_fork(g)

def has_k4(g):
    return g.subgraph_search(alpha_critical_easy[2], induced=True) is not None

def is_k4_free(g):
    return not has_k4(g)

def is_biclique(g):
    """
    a graph is a biclique if the vertices can be partitioned into 2 sets that induce cliques
    sage: is_biclique(p4)
    True
    sage: is_biclique(graphs.ButterflyGraph())
    True
    """
    gc = g.complement()
    return gc.is_bipartite()

def has_perfect_matching(g):
    n = g.order()
    if n%2 == 1:
        return False
    nu = g.matching(value_only=True)
    if 2*nu == n:
        return True
    else:
        return False

#true if radius equals diameter
def has_radius_equal_diameter(g):
    return g.radius() == g.diameter()

#true if residue equals independence number
def has_residue_equals_alpha(g):
    return residue(g) == independence_number(g)

def is_not_forest(g):
    return not g.is_forest()


def bipartite_double_cover(g):
    return g.tensor_product(graphs.CompleteGraph(2))

#replaced with faster LP-solver is_independence_irreducible
#has no non-empty critical independent set (<=> the only solution to the LP independence number relaxation is all 1/2's)
def has_empty_KE_part(g):
    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_bicritical(g):
    return has_empty_KE_part(g)


# Vizing's Theorem: chromatic index of any graph is either Delta or Delta+1
def is_class1(g):
    return chromatic_index(g) == max(g.degree())

def is_class2(g):
    return not(chromatic_index(g) == max(g.degree()))

def is_cubic(g):
    D = g.degree()
    return min(D) == 3 and max(D) == 3

#a property that applied to all entered hamiltonian graphs (before c60) but not the tutte graph, false for tutte graph
def is_anti_tutte(g):
    if not g.is_connected():
        return False
    return independence_number(g) <= g.diameter() + g.girth()

#a property that applied to all entered hamiltonian graphs upto c6cc6 but not the tutte graph, false for tutte graph
def is_anti_tutte2(g):
    if not g.is_connected():
        return False
    return independence_number(g) <=  domination_number(g) + g.radius()- 1

#for any graph diam <= 2*radius. this property is true in the extremal case
def diameter_equals_twice_radius(g):
    if not g.is_connected():
        return False
    return g.diameter() == 2*g.radius()

#for any graph diam >= radius. this property is true in the extremal case
def diameter_equals_radius(g):
    if not g.is_connected():
        return False
    return g.diameter() == g.radius()

#almost all graphs have diameter equals 2
def diameter_equals_two(g):
    if not g.is_connected():
        return False
    return g.diameter() == 2

def has_lovasz_theta_equals_alpha(g):
    if g.lovasz_theta() == independence_number(g):
        return True
    else:
        return False

def has_lovasz_theta_equals_cc(g):
    if g.lovasz_theta() == clique_covering_number(g):
        return True
    else:
        return False

#sufficient condition for hamiltonicity
def is_chvatal_erdos(g):
    return independence_number(g) <= vertex_con(g)


#matching_covered if every edge is in a maximum matching (generalization of factor-covered which requires perfect matching)
def matching_covered(g):
    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

#a property that separates tutte from known hamiltonian examples, must be connected
#radius(tutte) > center(tutte)
def radius_greater_than_center(g):
    if not g.is_connected() or g.radius() <= card_center(g):
        return False
    else:
        return True

#a property that separates tutte from known hamiltonian examples, must be connected
#avg_dist(tutte) > girth(tutte)
def avg_distance_greater_than_girth(g):
    if not g.is_connected() or g.average_distance() <= g.girth():
        return False
    else:
        return True

#chromatic number equals min of known chi upper bounds
def chi_equals_min_theory(g):
    chromatic_upper_theory = [brooks, wilf, welsh_powell, szekeres_wilf]
    min_theory = min([f(g) for f in chromatic_upper_theory])
    chi = chromatic_num(g)
    if min_theory == chi:
        return True
    else:
        return False

def is_heliotropic_plant(g):
    return (independence_number(g) == card_positive_eigenvalues(g))

def is_geotropic_plant(g):
    return (independence_number(g) == card_negative_eigenvalues(g))

#means has hamiltonian path, true iff g join a single vertex has hamiltonian cycle
def is_traceable(g):
     gadd = g.join(Graph(1),labels="integers")
     return gadd.is_hamiltonian()

def has_residue_equals_two(g):
    return residue(g) == 2

#a necessary condition for being even hole free
def is_chordal_or_not_perfect(g):
    if g.is_chordal():
        return true
    else:
        return not g.is_perfect()

def has_alpha_residue_equal_two(g):
    if residue(g) != 2:
        return false
    else:
        return independence_number(g) == 2

    # for vizing's independence number conjecture
def alpha_leq_order_over_two(g):
    return (2*independence_number(g) <= g.order())


#in a luo-zhao sufficient condition for alpha <= n/2 (vizing's ind number conj)
def order_leq_twice_max_degree(g):
    return (g.order() <= 2*max(g.degree()))

#not in properties list until meredith graph is computed
#critical if connected, class 2, and removal of any edge decreases chromatic number
def is_chromatic_index_critical(g):
    if not g.is_connected():
        return False
    Delta = max(g.degree())
    chi_e = chromatic_index(g)
    if chi_e != Delta + 1:
        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]

    for e in equiv_lines_representatives:
        gc = copy(g)
        gc.delete_edge(e)
        chi_e_prime = chromatic_index(gc)
        if not chi_e_prime < chi_e:
            return False
    return True

#not in properties list
#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(p3)
        False
        sage: is_factor_critical(c5)
        True
    """
    if g.order() % 2 == 0:
        return False
    for v in g.vertices():
        gc = copy(g)
        gc.delete_vertex(v)
        if not has_perfect_matching(gc):
            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):
                twin = w
                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

def is_cycle(g):
    return g.is_isomorphic(graphs.CycleGraph(g.order()))


#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
    n = g.order()
    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([min(lengths)..max(lengths)])

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([3..g.order()])

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))
    """
    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

######################################################################################################################
#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

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_two_connected = localise(is_two_connected)
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_haggkvist_nicoghossian,
is_generalized_dirac, is_van_den_heuvel, is_two_connected, is_three_connected,
is_lindquester, is_claw_free, has_perfect_matching, has_radius_equal_diameter,
is_not_forest, is_genghua_fan, is_cubic, diameter_equals_twice_radius,
diameter_equals_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, 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]

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, Graph.is_line_graph, 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]

removed_properties = [is_pebbling_class0]

#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

# Graph.is_prime removed as faulty 9/2014
# built in Graph.is_transitively_reduced removed 9/2014
# is_line_graph is theoretically efficient - but Sage's implementation is not 9/2014

# 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) - number_of_triangles(g)
add_to_lists(alpha_max_degree_minus_triangles_bound, alpha_lower_bounds, all_invariant_theorems)

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

def alpha_szekeres_wilf_bound(g):
    return ceil(order(x)/szekeres_wilf(x))
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^2 + 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) - number_of_triangles(g)
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

import pickle, os

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)
janko_kharaghani1800.name(new = "Janko-Kharagani 1800")

for graph in sage_graphs + [mathon_strongly_regular0, mathon_strongly_regular1, mathon_strongly_regular2, janko_kharaghani936, janko_kharaghani1800]:
    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([0..12])
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 * chromatic_number(x) + 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][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]???OG??qC???C??AC[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][email protected]@[email protected][email protected][email protected]???_???O??O??A??O???O?A?OB?C?AD???C`[email protected]???C?EC?O??GG`[email protected]?GA?_????????[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]????W??`[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????S??_o????????A??B??????_??C????C?')
ce84.name(new = "ce84")
add_to_lists(ce84, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= girth(x)^ceil(laplacian_energy(x))
ce85 = Graph('[email protected]`X?hB_?QKEo_op`C?|[email protected]?CBIlqf_GQ][email protected][email protected]?CCA?OG?')
ce85.name(new = "ce85")
add_to_lists(ce85, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= diameter(x)*residue(x) + different_degrees(x)
ce86 = Graph('SK|KWYc|^BJKlaCnMH^ECUoSC[{LHxfMG')
ce86.name(new = "ce86")
add_to_lists(ce86, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(max_common_neighbors(x), girth(x)^laplacian_energy(x))
ce87 = Graph('[email protected][email protected]@b?[[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]??AGC??AQ?QOc???Ow_?C[[email protected]@[email protected]@[email protected]@[email protected][email protected]?agAE??CpG?AA_`[email protected][email protected]@[email protected][email protected][email protected][email protected][email protected][email protected]?_DD`[email protected][email protected][email protected]@[email protected][email protected]@OM?_A?IOu`[email protected][email protected]@@[email protected][email protected][email protected]@?`@oA?_??OgC?K_G??G`[email protected]@B?A?HWc?HG??`[email protected]??IPAOdk`[email protected][email protected][email protected][email protected][email protected][email protected][email protected]_??_?_GGE`[email protected][email protected]_CB`[email protected][email protected]?RC[[email protected][email protected]?A??A?G?Ga_')
ce87.name(new = "ce87")
add_to_lists(ce87, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(radius(x), max_degree(x))^2
ce88 = Graph('[email protected]`[email protected]@????E???O?O???PO?O?_?G??`[email protected][email protected][email protected][email protected]?_?G')
ce88.name(new = "ce88")
add_to_lists(ce88, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= max_degree(x) + maximum(max_even_minus_even_horizontal(x), geometric_length_of_degree_sequence(x))
ce89 = Graph("[email protected]??`[email protected][email protected][email protected][email protected]????C???C?????G????")
ce89.name(new = "ce89")
add_to_lists(ce89, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= floor(arccosh(lovasz_theta(x)))^2
ce90 = Graph("[email protected]|wi\\fbna~}wepkkbXcrW}\\~NvtLKpY\\J_Ub^~yM~^tHnM}[email protected]{UOzzvr?L^PFi||[email protected]\YU{Vh]tWzwzpj\\n|kR]`Y}RpCvxk{rEMRP\\}|}dNdNtbO~yrkgMxlOXr|FvQ{tvfKKnHrp^}jV\\B^n\\LvLZeyX}QSKN^sm~yl\\[NJZXqdk]O|^zHl~vC{w`Nsn}x]utqrJozKXV|eIUUPv~ydc}]xJNWZjW|lpYm}{Jf~JWMixb^t]e|S~B[vKc{K[Kjut~}Kj~iAl\\tVNgyZadvoA}rdTlr\\\\wNr^^kJzrp|qlVy]siKncI~`oNm|ul\\PxDRyzddDzrjUn~ciOgbR}p~Cz|~MlxYoEVnVuZkxJgvmtE]]}~PRp[He]oBQz]PVJ~gVnvSUR|QF|`lomFh[j|jIaS~vh~_rYiiK}FnEW}ovnntxtRFBakzvwn[biJhNvf|VDV?m~Y]ndmfJQ|[email protected]~MCyn~{[email protected]}u|spOXzTVNY\\kjDNt\\zRMXxU|g|XrzFzDYiVvho}bQbyfI{{w[_~nrm}J~LhwH}TNmfM^}jqajl_ChY]M}unRK\\~ku")
ce90.name(new = "ce90")
add_to_lists(ce90, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(2*welsh_powell(x), max_even_minus_even_horizontal(x)^2)
ce91 = Graph("q?}x{k\FGNCRacDO`[email protected][email protected]@[email protected][email protected]@[email protected]@[email protected][email protected][email protected][email protected][email protected][email protected]??AO???S????CA?a??A?G??IOO????B?A???_??")
ce91.name(new = "ce91")
add_to_lists(ce91, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= -max_common_neighbors(x) + min_degree(x) - 1
ce92 = Graph("qR}fexr{J\\innanomndYrzmy^p~Ri]c]lA{~jVurv]n~reCed~|j{TtvnMtB~nZFrz{wUnV^fzV\\rUlt|qvJubnFwWSxxzfZ}Btj`yV~rv\\nknwl~Z?T]{qwn~bFzh^\\{Ezv}p~I^RV|oXe~knL~x^nNtvYlrezLX^tj{S^Rflqqv]e|S^}vpbe~Ni]m]}zfbZolnPl{N~}]X?")
ce92.name(new = "ce92")
add_to_lists(ce92, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= diameter for regular graphs
# Ryan Pepper, June 2017
ce93 = Graph('[email protected][email protected][email protected][email protected][email protected]_???G')
ce93.name(new = "ce93")
add_to_lists(ce93, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= diameter for regular graphs
# Ryan Pepper, June 2017
ce94 = Graph('[email protected][email protected][email protected]???AO??BG??B?')
ce94.name(new = "ce94")
add_to_lists(ce94, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= -average_distance(x) + ceil(lovasz_theta(x))
ce95 = Graph('[email protected]}gSGIZfc?Rkf{EWtVKJTmJtWYl_IoDOKOikwDSKtbH\\fi_g`affO\\|Agq`[email protected]?ylTR\\[email protected]{GiOWMUZX_puFP?')
ce95.name(new = "ce95")
add_to_lists(ce95, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= ceil(1/2*cvetkovic(x))
# CE to independence_number(x) >= 1/2*cvetkovic(x)
ce96 = Graph('Gvz~r{')
ce96.name(new = "ce96")
add_to_lists(ce96, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= -max_common_neighbors(x) + min_degree(x)
ce97 = Graph('eLvnv~yv{yJ~rlB^Mn|v^nz~V]mwVji}^vZf{\\\\nqZLfVBze}y[ym|jevvt~NNucret|~ejj~rz}Q\\~^an}XzTV~t]a]v}nx\\u]n{}~ffqjn`~e}lZvV]t_')
ce97.name(new = "ce97")
add_to_lists(ce97, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= lovasz_theta(x)/radius(x)
ce100 = Graph('[email protected]~~~~~~z~~~~~~~~^~~~~~z~~~~~~~~~~~~~~~v~~~v~~~~~~~~~~z~~~~~~~~^~~~~~~~~~}\~~}v~^~~}~~^~~~~~~~~~~~~^~~~~~~~~V~~~n~~n~~~~~~}~~|~}~~~~~~~~~~~~~~~~~~~~~vv~|~~~~~~~~~~~~~~~~~z~~w~~~~~~~~~~~~~~~~n~~~|~~~~~~~v~|~~~~~~~~~~}~|~r~V~~~n~~~~~~~~z~~}}~}~~~~vz~~z~~~z}~~~n~~~~~~~~~~~~n~~~~~~~z~~~~~~~~~~~~~~^~~~~~~~~~n~~]~~~~~n~~~}~~~~~~~~~~^~^~~~~}~~~~~~~~~~~z~~~~^~~~~~~w')
ce100.name(new = "ce100")
add_to_lists(ce100, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= matching_number(x) - order_automorphism_group(x) - 1
ce101 = Graph('I~~Lt~\Nw')
ce101.name(new = "ce101")
add_to_lists(ce101, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= card_positive_eigenvalues(x) - lovasz_theta(x)
ce102 = Graph('N^nN~~}Z~|}~~\~]zzw')
ce102.name(new = "ce102")
add_to_lists(ce102, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= card_negative_eigenvalues(x) - sigma_dist2(x)
ce103 = Graph('IOilnemjG')
ce103.name(new = "ce103")
add_to_lists(ce103, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= minimum(min_degree(x), floor(lovasz_theta(x)))
ce105 =  Graph('[email protected]@E?OYOSCPBTp?mOWaP_?W[OG[abE_?P[@[email protected][email protected]?CATE\[email protected][email protected][email protected]`?g?oDJqC?S?qJSqA?GN][email protected][email protected]?ygAACdcCMPA[d`[email protected][email protected][email protected][email protected][email protected][email protected][email protected]?G[cG_D[A_CbDKO[goBH_?S?')
ce105.name(new = "ce105")
add_to_lists(ce105, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= minimum(floor(lovasz_theta(x)), 10^laplacian_energy(x))
ce106 = Graph("k??????????????????????????????????????F~~~z~~~\~~~~{~^|nvny\^~~Njj~~zo}^yB|z~}h|Vv\Jft]~RlhV~tZMC^[email protected]\IVaJ}tvA\erD|Xx_rijkiIxLx}GE\pZ{yIwW?vV}K")
ce106.name(new = "ce106")
add_to_lists(ce106, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= max_even_minus_even_horizontal(x) + sinh(max_degree(x) - 1)
ce107 = Graph("[email protected][email protected][email protected][email protected][email protected]????????OG?G_?C????C??K????A?_O???O?O????O?O????OOG?G??????C???????g???????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][email protected][email protected]????")
ce107.name(new = "ce107")
add_to_lists(ce107, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= 10^cosh(log(residue(x)) - 1)
ce108 = Graph("U??????g}yRozOzw\wBn?zoBv_FN?Bn?B|??vO??")
ce108.name(new = "ce108")
add_to_lists(ce108, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= floor(caro_wei(x))^min_common_neighbors(x)
ce109 = Graph("Z???????????????????????????????B~~~v~~z~~|~nvnnjz~~xfntuV~w")
ce109.name(new = "ce109")
add_to_lists(ce109, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= min(card_positive_eigenvalues(x), 2*card_zero_eigenvalues(x))
ce110 = Graph("GUxvuw")
ce110.name(new = "ce110")
add_to_lists(ce110, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= minimum(lovasz_theta(x), max_degree(x)/card_center(x))
ce112 = Graph("flthktLhme|L|L]efhg|LbstFhhFhgbssG|L`FhiC]ecG|LCG|LaC]ew`FhnCG|L{Obstw`Fhlw`Fhi{ObssnCG|Ldw`FhmVaC]eknCG|LknCG|L??????_?????G")
ce112.name(new = "ce112")
add_to_lists(ce112, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(e^average_distance(x), max_degree(x)^2)
ce114 = Graph("[email protected][email protected][email protected][email protected][email protected][email protected]?AO???G_?AAG_?????o???????????????I??DG????????G??A_????C??O?G??_?_?????_G???????`[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???_??O??`[email protected]?OOC??C???_?????")
ce114.name(new = "ce114")
add_to_lists(ce114, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= 2*wilf(x)^2 + radius(x)
ce115 = Graph("[email protected][email protected][email protected][email protected]???_?S??????I???C???O?G????????G??C?_????A_??CG?A?????????_????A????????????????G???C???????????CC?G???C?????_????????o?I???_???????")
ce115.name(new = "ce115")
add_to_lists(ce115, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= card_periphery(x) + floor(e^laplacian_energy(x))
ce116 = Graph("J?Bzvrw}Fo?")
ce116.name(new = "ce116")
add_to_lists(ce116, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= residue(x)^2/density(x)
ce117 = Graph("N???F~}~f{^_z_~_^o?")
ce117.name(new = "ce117")
add_to_lists(ce117, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(caro_wei(x), e^different_degrees(x))^2
ce118 = Graph("O????B~~v}^w~o~o^wF}?")
ce118.name(new = "ce118")
add_to_lists(ce118, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= 10^sinh(average_vertex_temperature(x) + card_center(x))
ce119 = Graph("\[email protected][email protected]????g????")
ce119.name(new = "ce119")
add_to_lists(ce119, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= maximum(girth(x), min_degree(x))^laplacian_energy(x)
ce120 = Graph("^????????????????????X~~Umf|mezrBcjoezwF^{_Un}?|w{?kQ[[email protected]}?FNl??Etw??Oz??F~Z_??")
ce120.name(new = "ce120")
add_to_lists(ce120, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= (2*girth(x))^card_periphery(x)
ce121 = 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][email protected][email protected][email protected][email protected]")
ce121.name(new = "ce121")
add_to_lists(ce121, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= ceil(laplacian_energy(x)*max_degree(x))
ce122 = Graph("[email protected]??????????????????????????????????????????????????????????????????????????????????B\jeRlsk[rya~Sdr[HeojcW}xwcX_TgTVa?UhcYC?BTaaSo?}[email protected]@_b?EysEu}?Do`[email protected]??~AHGh_?Awyl{w??TrUZDg??AuxBGO??FJ{LUo??O_IF]g??EVmFSY???`YcP_????l|v`}???Bg_[ge???ERCdO[???APuTc^????NQUWCO???B[QrBO????BMP^A_????eo{v`_????NgB\A_????O[[email protected][email protected]_oTC?????FCDLPo????AECLPI?????DqZqCE??????")
ce122.name(new = "ce122")
add_to_lists(ce122, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= minimum(cvetkovic(x), 10^laplacian_energy(x))
ce123 = Graph("`??????????????????????????????????????????^^}nx~~[~~x}^k~~F~v^o^[email protected]^~~wF~v}_F~~^_B~~~W?")
ce123.name(new = "ce123")
add_to_lists(ce123, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= minimum(fractional_alpha(x), 10^laplacian_energy(x))
ce124 = Graph("Z????????????????????~~~~~v~vf|~b~~o~~sF~~_^~}?~|k?z~w?^~}??")
ce124.name(new = "ce124")
add_to_lists(ce124, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= ceil(e^caro_wei(x))
ce125 = Graph("L??F~z{~FwN_~?")
ce125.name(new = "ce125")
add_to_lists(ce125, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= ceil(e^inverse_degree(x))
ce126 = Graph("Ov~~~}Lvs]^~~~~t~~}yJ")
ce126.name(new = "ce126")
add_to_lists(ce126, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= minimum(annihilation_number(x), 10^laplacian_energy(x))
ce127 = Graph("[??????~~~^{~w~w^{F~?~WB~_F~?F~?B~_?~w?F~??^s??~w??~w??^{??F~???")
ce127.name(new = "ce127")
add_to_lists(ce127, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= (diameter(x) + 1)*residue(x)
ce128 = Graph("M????B~~v}^w~o~o?")
ce128.name(new = "ce128")
add_to_lists(ce128, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= floor(10^sqrt(average_distance(x)))
ce129 = Graph("X????????????????????????????F~~~~z~~~Z~~{n}|u~utn~")
ce129.name(new = "ce129")
add_to_lists(ce129, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= minimum(lovasz_theta(x), 10^laplacian_energy(x))
ce130 = Graph("]?????????????????F|~nzz~~f~~F|~B~~_~~WF~~?^~{?nng?~~w?^^{[email protected]~~_??")
ce130.name(new = "ce130")
add_to_lists(ce130, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= (residue(x) + 1)*girth(x)
ce131 = Graph("W?????????^~~}~}^~F~o~}B~wF}oF~oB~w?~}?F~o?^~??")
ce131.name(new = "ce131")
add_to_lists(ce131, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) <= minimum(size(x), 10^laplacian_energy(x))
ce132 = Graph("b????????????????????~~|~~|}~x~n~vp~{Nz{^e~svN}Xc~zFKZ~uyX[z[J\\[email protected][email protected]]}X{SzQZQQ^posGNlZg?R}lp`LX{L?")
ce132.name(new = "ce132")
add_to_lists(ce132, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= -brinkmann_steffen(x) - girth(x) + matching_number(x)
ce133 = Graph("[email protected]^v~_?UMVuzfYa_~}|tWZ}v~~v}WgheAI[pTRjr\\Wv}y~VeypzF\\^zmq}C\\UFoD^XJFQwvU^AovUND~XnF]STE_EF~v^~~JF\\X{X\\VFoeMvmy~xzZv\\^{|n~v~~~^v}y~xz]Wihy_Lzmq]CxSawvUNFZr]zj~fl|vMy~wz^Z}q}MxvsZv\\^{|nnuMy~wr^\\vmy~xz^^z~\\^}|nny{[email protected]|vV~NZz~i}vUNnZr~n]zj~fl|vr^u~p~~}~~z}v}N~~v~~nzNwzf^\\n~TuQodI]AHvuMy^wr^\\wkNz^w~|~^}~y}vUNNZr~n~v}y~|z^^|~~^zn~~n~~v~y}q]MxVtZn|y{qUMHRpZfx|WyhIbL|vap[~}~~~~~~~~~}|vV~NZz~fz~jzHWydNDmzvz~~~~~~~~~~~~c?AGgA]Kw_PC_?_???O?????V~v~~~^~~n~~}\\[email protected]~z~N~~~~~~~}Zaw}?oscOOx?d}ptR|EZznDbxsj~z~~~~~~~~~}^cAAYgA^KwgPCc]~v^~~^~~n~~}znz\\w~|~^}~~~r|v}y~|z^^|~~~t^Vuyp|z]^|~~~dZz~\\^{|nn}~~~ynw")
ce133.name(new = "ce133")
add_to_lists(ce133, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= -max_common_neighbors(x) + min_degree(x) - 1
ce134 = Graph('rQjxS{d~tvtrkz~pIJZ{gflAUdYPfybdzswqqS~i`~EfCmswgpu[zfAxLl\TtJEFlilHnZicmo}ZYJjAluT]d|scS\LgJ[|cs~}TBXxNQnJxSm]}oSMt{\kxUl|UhPZHlz`smizxCPTiNL[Mv|kbKUI}^r}oiAdMLE\^rga{v][email protected]]Hb}wupjLh`Yg|Rn|`b[iLNp}Oudo~r_`oFEjTzvw')
ce134.name(new = "ce134")
add_to_lists(ce134, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= floor(tan(brooks(x)))
ce135 = Graph('Nzx~VT}yzxNd^J^Jn~w')
ce135.name(new = "ce135")
add_to_lists(ce135, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= floor(lovasz_theta(x))*sin(gutman_energy(x))
paley_17 = graphs.PaleyGraph(17)
paley_17.name(new = "paley_17")
add_to_lists(paley_17, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= ceil(lovasz_theta(x)) - diameter(x)
# CE to independence_number(x) >= ceil(lovasz_theta(x)) - radius(x)
paley_37 = graphs.PaleyGraph(37)
paley_37.name(new = "paley_37")
add_to_lists(paley_37, graph_objects, counter_examples, all_graphs)

# CE to independence_number(x) >= minimum(floor(lovasz_theta(x)), tan(randic(x)))
paley_53e = graphs.PaleyGraph(53)
paley_53e.add_edge(52,53)
paley_53e.name(new = "paley_53e")
add_to_lists(paley_53e, graph_objects, counter_examples, all_graphs)

paley_101 = graphs.PaleyGraph(101)
paley_101.name(new = "paley_101")
add_to_lists(paley_101, graph_objects, all_graphs)

# CE to independence_number(x) >= cos(alon_spencer(x))*floor(lovasz_theta(x))
paley_149 = graphs.PaleyGraph(149)
paley_149.name(new = "paley_149")
add_to_lists(paley_149, graph_objects, counter_examples, all_graphs)

#a K5 with a pendant
# CE to dirac => regular or planar
k5pendant = Graph('E~}?')
k5pendant.name(new="k5pendant")
add_to_lists(k5pendant, graph_objects, counter_examples, all_graphs)

#alon_seymour graph:
# CE to the rank-coloring conjecture,
# 56-regular, vertex_trans, alpha=2, omega=22, chi=chi'=edge_connect=56
alon_seymour=Graph([[0..63], lambda x,y : operator.xor(x,y) not in (0,1,2,4,8,16,32,63)])
alon_seymour.name(new="alon_seymour")
add_to_lists(alon_seymour, problem_graphs, counter_examples, all_graphs)

edge_critical_5=graphs.CycleGraph(5)
edge_critical_5.add_edge(0,3)
edge_critical_5.add_edge(1,4)
edge_critical_5.name(new="edge_critical_5")
add_to_lists(edge_critical_5, graph_objects, chromatic_index_critical, all_graphs)

# CE to independence_number(x) >= min(e - n + 1, diameter(x))
heather = graphs.CompleteGraph(4)
heather.add_vertex()
heather.add_vertex()
heather.add_edge(0,4)
heather.add_edge(5,4)
heather.name(new="heather")
add_to_lists(heather, graph_objects, counter_examples, all_graphs)

#residue = alpha = 3
# CE to residue = alpha => is_ore
ryan3=graphs.CycleGraph(15)
for i in range(15):
    for j in [1,2,3]:
        ryan3.add_edge(i,(i+j)%15)
        ryan3.add_edge(i,(i-j)%15)
ryan3.name(new="ryan3")
add_to_lists(ryan3, graph_objects, counter_examples, all_graphs)

#sylvester graph: 3-reg, 3 bridges, no perfect matching (why Petersen theorem requires no more than 2 bridges)
sylvester = Graph('[email protected][email protected][email protected][email protected]`A')
sylvester.name(new="sylvester")
add_to_lists(sylvester, graph_objects, all_graphs)

fork = graphs.PathGraph(4)
fork.add_vertex()
fork.add_edge(1,4)
fork.name(new="fork")
add_to_lists(fork, graph_objects, all_graphs)

# one of the 2 order 11 chromatic edge-critical graphs discovered by brinkmann and steffen
edge_critical_11_1 = graphs.CycleGraph(11)
edge_critical_11_1.add_edge(0,2)
edge_critical_11_1.add_edge(1,6)
edge_critical_11_1.add_edge(3,8)
edge_critical_11_1.add_edge(5,9)
edge_critical_11_1.name(new="edge_critical_11_1")
add_to_lists(edge_critical_11_1, graph_objects, chromatic_index_critical, all_graphs)

#one of the 2 order 11 chromatic edge-critical graphs discovered by brinkmann and steffen
edge_critical_11_2 = graphs.CycleGraph(11)
edge_critical_11_2.add_edge(0,2)
edge_critical_11_2.add_edge(3,7)
edge_critical_11_2.add_edge(6,10)
edge_critical_11_2.add_edge(4,9)
edge_critical_11_2.name(new="edge_critical_11_2")
add_to_lists(edge_critical_11_2, graph_objects, chromatic_index_critical, all_graphs)

# chromatic_index_critical but not overfull
pete_minus=graphs.PetersenGraph()
pete_minus.delete_vertex(9)
pete_minus.name(new="pete_minus")
add_to_lists(pete_minus, graph_objects, chromatic_index_critical, all_graphs)

"""
The Haemers graph was considered by Haemers who showed that alpha(G)=theta(G)<vartheta(G).
The graph is a 108-regular graph on 220 vertices. The vertices correspond to the 3-element
subsets of {1,...,12} and two such vertices are adjacent whenever the subsets
intersect in exactly one element.

    sage: haemers
    haemers: Graph on 220 vertices
    sage: haemers.is_regular()
    True
    sage: max(haemers.degree())
    108
"""
haemers = Graph([Subsets(12,3), lambda s1,s2: len(s1.intersection(s2))==1])
haemers.relabel()
haemers.name(new="haemers")
add_to_lists(haemers, problem_graphs, all_graphs)

"""
The Pepper residue graph was described by Ryan Pepper in personal communication.
It is a graph which demonstrates that the residue is not monotone. The graph is
constructed by taking the complete graph on 3 vertices and attaching a pendant
vertex to each of its vertices, then taking two copies of this graph, adding a
vertex and connecting it to all the pendant vertices. This vertex has degree
sequence [6, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2] which gives residue equal to 4.
By removing the central vertex with degree 6, you get a graph with degree
sequence [3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1] which has residue equal to 5.

    sage: pepper_residue_graph
    pepper_residue_graph: Graph on 13 vertices
    sage: sorted(pepper_residue_graph.degree(), reverse=True)
    [6, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2]
    sage: residue(pepper_residue_graph)
    4
    sage: residue(pepper_residue_graph.subgraph(vertex_property=lambda v:pepper_residue_graph.degree(v)<6))
    5
"""
pepper_residue_graph = graphs.CompleteGraph(3)
pepper_residue_graph.add_edges([(i,i+3) for i in range(3)])
pepper_residue_graph = pepper_residue_graph.disjoint_union(pepper_residue_graph)
pepper_residue_graph.add_edges([(0,v) for v in pepper_residue_graph.vertices() if pepper_residue_graph.degree(v)==1])
pepper_residue_graph.relabel()
pepper_residue_graph.name(new="pepper_residue_graph")
add_to_lists(pepper_residue_graph, graph_objects, all_graphs)

"""
The Barrus graph was suggested by Mike Barrus in "Havel-Hakimi residues of Unigraphs" (2012) as an example of a graph whose residue (2) is
less than the independence number of any realization of the degree sequence. The degree sequence is [4^8,2].
The realization is the one given by reversing the Havel-Hakimi process.

    sage: barrus_graph
    barrus_graph: Graph on 9 vertices
    sage: residue(barrus_graph)
    2
    sage: independence_number(barrus_graph)
    3
"""
barrus_graph = Graph('HxNEG{W')
barrus_graph.name(new = "barrus_graph")
add_to_lists(barrus_graph, graph_objects, all_graphs)

# CE to (is_split)->((is_eulerian)->(is_regular))
# split graph from k4 and e2 that is eulerian but not regular
# isomorphic to c6 with a k4 subgraph
# eulerain, diameter = 3, radius=2, hamiltonian

k4e2split = graphs.CompleteGraph(4)
k4e2split.add_vertices([4,5])
k4e2split.add_edge(4,0)
k4e2split.add_edge(4,1)
k4e2split.add_edge(5,2)
k4e2split.add_edge(5,3)
k4e2split.name(new = "k4e2split")
add_to_lists(k4e2split, graph_objects, counter_examples, all_graphs)

# CE to (has_residue_equals_alpha)->((is_eulerian)->(alpha_leq_order_over_two))
triangle_star = Graph("H}[email protected]_")
triangle_star.name(new = "triangle_star")
add_to_lists(triangle_star, graph_objects, counter_examples, all_graphs)

#flower with n petals
def flower(n):
    g = graphs.StarGraph(2*n)
    for x in range(n):
        v = 2*x+1
        g.add_edge(v,v+1)
    return g

flower_with_3_petals = flower(3)
flower_with_3_petals.name(new = "flower_with_3_petals")
add_to_lists(flower_with_3_petals, graph_objects, all_graphs)

flower_with_4_petals = flower(4)
flower_with_4_petals.name(new = "flower_with_4_petals")
add_to_lists(flower_with_4_petals, graph_objects, all_graphs)

# Gallai Tree graph
gallai_tree = Graph("`[email protected][email protected][email protected][email protected][email protected][email protected]_??F???N????_???G???B????C????W????G????G????C")
gallai_tree.name(new = "gallai_tree")
add_to_lists(gallai_tree, graph_objects, all_graphs)

# Trigonal Antiprism w/ capped top face
trig_antiprism_capped = Graph("Iw?EthkF?")
trig_antiprism_capped.name(new = "trig_antiprism_capped")
add_to_lists(trig_antiprism_capped, graph_objects, all_graphs)

"""
From Willis's thesis, page 4
Alpha = Fractional Alpha = 4

    sage: independence_number(willis_page4)
    4
    sage: fractional_alpha(willis_page4)
    4
"""
willis_page4 = Graph("GlCKIS")
willis_page4.name(new = "willis_page4")
add_to_lists(willis_page4, graph_objects, all_graphs)

"""
From Willis's thesis, page 7

    sage: willis_page7.radius()
    2
    sage: average_distance(willis_page7)
    1.467
"""
willis_page7 = Graph("ELRW")
willis_page7.name(new = "willis_page7")
add_to_lists(willis_page7, graph_objects, all_graphs)

"""
From Willis's thesis, page 13, Fig. 2.7

    sage: independence_number(willis_page13_fig27)
    4
    sage: willis_page13_fig27.order()
    7
    sage: willis_page13_fig27.size()
    15
"""
willis_page13_fig27 = Graph("Fs\zw")
willis_page13_fig27.name(new = "willis_page13_fig27")
add_to_lists(willis_page13_fig27, graph_objects, all_graphs)

"""
From Willis's thesis, page 10, Figure 2.2
Graph for which the Cvetkovic bound is the best upper bound present in the thesis

    sage: independence_number(willis_page10_fig23)
    4
    sage: willis_page10_fig23.order()
    10
    sage: willis_page10_fig23.size()
    15
    sage: max_degree(willis_page10_fig23)
    3
    sage: min_degree(willis_page10_fig23)
    3
"""
willis_page10_fig23 = Graph("G|eKHw")
willis_page10_fig23.name(new = "willis_page10_fig23")
add_to_lists(willis_page10_fig23, graph_objects, all_graphs)

"""
From Willis's thesis, page 10, Figure 2.4
Graph for which the Cvetkovic bound is the best upper bound present in the thesis

    sage: independence_number(willis_page10_fig24)
    9
    sage: willis_page10_fig24.order()
    24
    sage: willis_page10_fig24.size()
    36
    sage: max_degree(willis_page10_fig24)
    3
    sage: min_degree(willis_page10_fig24)
    3
"""
willis_page10_fig24 = Graph("[email protected][email protected][email protected][email protected][email protected][email protected]")
willis_page10_fig24.name(new = "willis_page10_fig24")
add_to_lists(willis_page10_fig24, graph_objects, all_graphs)

"""
From Willis's thesis, page 13, Figure 2.6
Graph for which the fractional independence bound is the best upper bound present in the thesis

    sage: independence_number(willis_page13_fig26)
    3
    sage: willis_page13_fig26.order()
    7
    sage: willis_page13_fig26.size()
    12
    sage: max_degree(willis_page13_fig26)
    4
    sage: min_degree(willis_page13_fig26)
    3
"""
willis_page13_fig26 = Graph("FstpW")
willis_page13_fig26.name(new = "willis_page13_fig26")
add_to_lists(willis_page13_fig26, graph_objects, all_graphs)

"""
From Willis's thesis, page 21, Figure 3.1
Graph for which n/chi is the best lower bound present in the thesis

    sage: independence_number(willis_page21)
    4
    sage: willis_page21.order()
    12
    sage: willis_page21.size()
    20
    sage: max_degree(willis_page21)
    4
    sage: chromatic_num(willis_page21)
    3
"""
willis_page21 = Graph("[email protected]")
willis_page21.name(new = "willis_page21")
add_to_lists(willis_page21, graph_objects, all_graphs)

"""
From Willis's thesis, page 25, Figure 3.2
Graph for which residue is the best lower bound present in the thesis

    sage: independence_number(willis_page25_fig32)
    3
    sage: willis_page25_fig32.order()
    8
    sage: willis_page25_fig32.size()
    15
    sage: max_degree(willis_page25_fig32)
    6
    sage: chromatic_num(willis_page25_fig32)
    4
"""
willis_page25_fig32 = Graph("[email protected]@~w")
willis_page25_fig32.name(new = "willis_page25_fig32")<