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)
return gdub

def neighbors_set(g,S):
N = set()
for v in S:
for n in g.neighbors(v):
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

"""
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:
for v in g.vertices():
if v != new_v:
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():
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())
last_cycle = g.vertices()[-4:]
for v in last_cycle:
iters += 1
return g

def find_all_triangles(g):
E = g.edges()
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():
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)):
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_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():
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:
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!"

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

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

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

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

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

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

def median_degree(g):
return median(g.degree())

def inverse_degree(g):
return sum([(1.0/d) for d in g.degree() if d!= 0])

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

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

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)

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

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)

def annihilation_number(g):
seq = sorted(g.degree())

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

return a

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():

for (u,v) in g.edge_iterator(labels=False):

return p.solve()

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():

for (u,v) in g.edge_iterator(labels=False):

return p.solve()

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

def cycle_space_dimension(g):
return g.size()-g.order()+g.connected_components_number()

def card_center(g):
return len(g.center())

def card_periphery(g):
return len(g.periphery())

def max_eigenvalue(g):

def min_eigenvalue(g):

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

def largest_singular_value(g):
svd = A.SVD()
sigma = svd[1]
return sigma[0,0]

def card_max_cut(g):
return g.max_cut(value_only=True)

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

#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

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

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

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

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

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

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

#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

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)

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

#sum of the positive eigenvalues of a graph
def gutman_energy(g):
Ls = [lam for lam in L if lam > 0]
return sum(Ls)

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

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

def graph_rank(g):

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

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

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

def card_cut_vertices(g):
return len((g.blocks_and_cut_vertices())[1])

def card_connectors(g):
return g.order() - card_cut_vertices(g)

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

def vertex_con(g):
return g.vertex_connectivity()

def edge_con(g):
return g.edge_connectivity()

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

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

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

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

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

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

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

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

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

def card_independence_irreducible_part(g):
return len(find_independence_irreducible_part(g))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)

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

def max_local_density(g):
"""
sage: max_local_density(p3)
1
sage: max_local_density(paw)
1
"""
return max(local_density(g))

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)

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

# 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

# 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

def max_minus_min_degrees(g):
return max_degree(g) - min_degree(g)

def randic_irregularity(g):
return order(g)/2 - randic(g)

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()]])

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

def one_over_size_sedd(g):
return 1/g.size() * sum_edges_degree_difference(g)

def largest_eigenvalue_minus_avg_degree(g):
return max_eigenvalue(g) - g.average_degree()

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

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

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

def min_centrality_closeness(g):
centralities = g.centrality_closeness()
return centralities[min(centralities)]

def max_centrality_closeness(g):
centralities = g.centrality_closeness()
return centralities[max(centralities)]

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

def min_centrality_degree(g):
centralities = g.centrality_degree()
return centralities[min(centralities)]

def max_centrality_degree(g):
centralities = g.centrality_degree()
return centralities[max(centralities)]

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

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]

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

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:

# 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]
return g.order()
else:
return min( len(union(g.neighbors(v), g.neighbors(w))) for (v,w) in nonadj)

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)

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

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

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

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

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

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

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

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

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

def independence_number(g):
return g.independent_set(value_only=True)

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)

def chromatic_num(g):
return g.chromatic_number()

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

def n_over_alpha(g):
n = g.order() + 0.0
return n/independence_number(g)

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

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

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

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

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

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

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

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

# 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

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

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

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

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)

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

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

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)

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

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

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

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 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
if not g.is_connected():
return False

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

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

#a property that separates tutte from known hamiltonian examples, must be connected
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):

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
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*
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):
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)
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_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

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

# 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

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

# Trivial
alpha_trivial_bound = Graph.order

# Lovasz Theta
alpha_lovasz_theta_bound = Graph.lovasz_theta

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

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

# Matching Number - Folklore
def alpha_matching_number_bound(g):
return order(g) - matching_number(g)

# Min-Degree Theorm
def alpha_min_degree_bound(g):
return order(g) - min_degree(g)

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

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

# 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

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

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

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

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

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

# Three Bounds on the Independence Number of a Graph - C. E. Larson, R. Pepper
return (g.radius() + (card_pendants(g)/2) - 1)

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

def alpha_max_degree_minus_triangles_bound(g):
return max_degree(g) - number_of_triangles(g)

def alpha_order_brooks_bound(g):
return ceil(order(x)/brooks(x))

def alpha_szekeres_wilf_bound(g):
return ceil(order(x)/szekeres_wilf(x))

def alpha_welsh_powell_bound(g):
return ceil(g.order()/welsh_powell(g))

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)

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

alpha_average_distance_bound = Graph.average_distance

alpha_residue_bound = residue

alpha_max_even_minus_even_horizontal_bound = max_even_minus_even_horizontal

alpha_critical_independence_number_bound = critical_independence_number

def alpha_max_degree_minus_number_of_triangles_bound(g):
return max_degree(g) - number_of_triangles(g)

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

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

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()]))

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

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)

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

# 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

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

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

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

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

# 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

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

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

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

# Ronald Gould, Updating the Hamiltonian problem — a survey. Journal of Graph Theory 15.2: 121-157, 1991.

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

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

#############################################################################
# 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:
except Exception as e:
print("The Cameron graph was not loaded. Caused by:")
print(e)

try:
except Exception as e:
print("The M22 graph was not loaded. Caused by:")
print(e)

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

try:
except Exception as e:
print("The McLaughlin graph was not loaded. Caused by:")
print(e)

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

#hard built-in Sage graphs

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

try:
cell120 = graphs.Cell120()
cell120.name(new = "Cell120")
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")
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]:

# Meredith graph is 4-reg, class2, non-hamiltonian: http://en.wikipedia.org/wiki/Meredith_graph

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

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

alpha_critical_hard = [Graph('Hj\\x{F{')]
for g in alpha_critical_hard:

# Graph objects

p3 = graphs.PathGraph(3)
p3.name(new = "p3")

p4 = graphs.PathGraph(4)
p4.name(new="p4")

p5 = graphs.PathGraph(5)
p5.name(new = "p5")

p6 = graphs.PathGraph(6)
p6.name(new="p6")

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

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

# CE to independence_number(x) <= 2*cvetkovic(x)*log(10)/log(x.size())
p102 = graphs.PathGraph(102)
p102.name(new = "p102")

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

c6 = graphs.CycleGraph(6)
c6.name(new = "c6")

# CE to independence_number(x) <= (e^welsh_powell(x) - graph_rank(x))^2
c22 = graphs.CycleGraph(22)
c22.name(new = "c22")

# CE to independence_number(x) <= minimum(cvetkovic(x), 2*e^sum_temperatures(x))
c34 = graphs.CycleGraph(34)
c34.name(new = "c34")

# CE to independence_number(x) <= residue(x)^(degree_sum(x)^density(x))
c102 = graphs.CycleGraph(102)
c102.name(new = "c102")

"""
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.name(new = "c13_2")

k3 = alpha_critical_easy[1]
k4 = alpha_critical_easy[2]

k10 = graphs.CompleteGraph(10)
k10.name(new="k10")

# CE to independence_number(x) >= floor(tan(floor(gutman_energy(x))))
k37 = graphs.CompleteGraph(37)
k37.name(new = "k37")

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

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

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

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

k5_3=graphs.CompleteBipartiteGraph(5,3)
k5_3.name(new = "k5_3")

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

#two c4's joined at a vertex
c4c4=graphs.CycleGraph(4)
for i in [4,5,6]:
c4c4.name(new="c4c4")

#two c5's joined at a vertex: eulerian, not perfect, not hamiltonian
c5c5=graphs.CycleGraph(5)
for i in [5,6,7,8]:
c5c5.name(new="c5c5")

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.name(new="regular_non_trans")

c6ee = graphs.CycleGraph(6)
c6ee.name(new="c6ee")

#c6ee plus another chord: hamiltonian, regular, vertex transitive
c6eee = copy(c6ee)
c6eee.name(new="c6eee")

#c8 plus one long vertical chord and 3 parallel horizontal chords
c8chorded = graphs.CycleGraph(8)
c8chorded.name(new="c8chorded")

#c8 plus 2 parallel chords: hamiltonian, tri-free, not vertex-transitive
c8chords = graphs.CycleGraph(8)
c8chords.name(new="c8chords")

# C10 with an edge through the center
c10e = graphs.CycleGraph(10)
c10e.name(new = "c10e")

# C10e with another edge through center
c10ee = graphs.CycleGraph(10)
c10ee.name(new = "c10ee")

prismsub = graphs.CycleGraph(6)
prismsub.subdivide_edge(1,4,1)
prismsub.name(new="prismsub")

# ham, not vertex trans, tri-free, not cartesian product
prismy = graphs.CycleGraph(8)
prismy.name(new="prismy")

#c10 with chords, ham, tri-free, regular, planar, vertex transitive
sixfour = graphs.CycleGraph(10)
sixfour.name(new="sixfour")

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

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

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

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

#an example of a bipartite, 1-tough, not van_den_heuvel, not hamiltonian graph
kratsch_lehel_muller = graphs.PathGraph(12)
kratsch_lehel_muller.name(new="kratsch_lehel_muller")

#ham, not planar, not anti_tutte
c6xc6 = graphs.CycleGraph(6).cartesian_product(graphs.CycleGraph(6))
c6xc6.name(new="c6xc6")

c7xc7 = graphs.CycleGraph(7).cartesian_product(graphs.CycleGraph(7))
c7xc7.name(new="c7xc7")

# Product Graphs, fig. 1.13
c6xk2 = graphs.CycleGraph(6).cartesian_product(graphs.CompleteGraph(2))
c6xk2.name(new = "c6xk2")

# Product Graphs, fig. 1.13
k1_4xp3 = graphs.CompleteBipartiteGraph(1, 4).cartesian_product(graphs.PathGraph(3))
k1_4xp3.name(new = "k1_4xp3")

# Product Graphs, fig. 1.14
p4xk3xk2 = graphs.PathGraph(4).cartesian_product(graphs.CompleteGraph(3)).cartesian_product(graphs.CompleteGraph(2))
p4xk3xk2.name(new = "p4xk3xk2")

# Product Graphs, fig. 4.1
p3xk2xk2 = graphs.PathGraph(3).cartesian_product(graphs.CompleteGraph(2)).cartesian_product(graphs.CompleteGraph(2))
p3xk2xk2.name(new = "p3xk2xk2")

# Product Graphs, fig. 5.1
p4Xp5 = graphs.PathGraph(4).strong_product(graphs.PathGraph(5))
p4Xp5.name(new = "p4Xp5")

# Product Graphs, Fig 6.1
k3lxp3 = graphs.CompleteGraph(3).lexicographic_product(graphs.PathGraph(3))
k3lxp3.name(new = "k3lxp3")

# Product Graphs, Fig 6.1
p3lxk3 = graphs.PathGraph(3).lexicographic_product(graphs.CompleteGraph(3))
p3lxk3.name(new = "p3lxk3")

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

#non-ham, 2-connected, eulerian (4-regular)
gould = Graph('[email protected]')
gould.name(new="gould")

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

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

#similar to throwing2 with pair of edges swapped, non-hamiltonian
throwing3 = Graph("K~wWGGB?oD_N")
throwing3.name(new="throwing3")

#graph has diameter != radius but is hamiltonian
tent = graphs.CycleGraph(4).join(Graph(1),labels="integers")
tent.name(new="tent")

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

# nico found the smallest hamiltonian overfull graph
non_ham_over = Graph("HCQRRQo")
non_ham_over.name(new="non_ham_over")

# From Ryan Pepper
ryan = Graph("[email protected]?OC?AW???O?C??B???G?A?_??R")
ryan.name(new="ryan")

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

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

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

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

# CE to independence_number(x) <= 2 * girth(x)^2 + 2
# Star with 22 rays plus extra edge
s22e = graphs.StarGraph(22)
s22e.name(new="s22e")

# Graph from delavina's jets paper
starfish = Graph('N~~eeQoiCoM?Y?U?F??')
starfish.name(new="starfish")

# difficult graph from INP: order=11, alpha=4, best lower bound < 3
difficult11 = Graph('J?FBo{fdb?')
difficult11.name(new="difficult11")

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

# mycielskian of a triangle:
# CE to chi <= max(clique, nu)
# chi=4, nu = clique = 3
c3mycielski = Graph('FJnV?')
c3mycielski.name(new="c3mycieski")

# 4th mycielskian of a triangle,
# CE to chi <= clique + girth
# chi = 7, clique = girth = 3
c3mycielski4 = Graph('[email protected]@[email protected]?NyBqLepJTgRXkAkU?JPg?VB_?W[[email protected]???Bs???Bw???A??F~~_B}?^sBo[MOuZErWatYUjObXkZL_QpWUJ?CsYEbO?fB_w[?A[email protected]???Ds?M_???V_?{????oB}?????o[M?????WuZ?????EUjO?????rXk?????BUJ??????EsY??????Ew[??????Bo???????xk???????FU_???????\\k????????|_????????}_????????^_?????????')
c3mycielski4.name(new="c3mycielski4")

# A PAW is a traingle with a pendant
# Shows up in a sufficient condition for hamiltonicity
paw=Graph('C{')
paw.name(new="paw")

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

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

#a DART is a kite with a pendant
dart = Graph('DnC')
dart.name(new="dart")

# CE to ((is_chordal)^(is_forest))->(has_residue_equals_alpha)
ce2=Graph("HdGkCA?")
ce2.name(new = "ce2")

# CE to ((~(is_planar))&(is_chordal))->(has_residue_equals_alpha)
ce4=Graph("G~sNp?")
ce4.name(new = "ce4")

# CE to (((is_line_graph)&(is_cartesian_product))|(is_split))->(has_residue_equals_alpha)
ce5=Graph("X~}AHKVB{GGPGRCJB{GOOCAWAwO}CGOOAHACHaCGVACG^")
ce5.name(new = "ce5")

# CE to (is_split)->((order_leq_twice_max_degree)&(is_chordal))
ce6 = Graph("[email protected]")
ce6.name(new = "ce6")

# CE to (has_residue_equals_alpha)->((is_bipartite)->(order_leq_twice_max_degree))
ce7 = Graph("FpGK?")
ce7.name(new = "ce7")

# CE to ((has_paw)&(is_circular_planar))->(has_residue_equals_alpha)
ce8 = Graph('[email protected]_G')
ce8.name(new = "ce8")

# CE to ((has_H)&(is_forest))->(has_residue_equals_alpha)
ce9 = Graph('IhCGGD?G?')
ce9.name(new = "ce9")

# CE to (((is_eulerian)&(is_planar))&(has_paw))->(has_residue_equals_alpha)
ce10=Graph('[email protected][email protected]')
ce10.name(new = "ce10")

# CE to (((is_cubic)&(is_triangle_free))&(is_H_free))->(has_residue_equals_two)
ce12 = Graph("Edo_")
ce12.name(new = "ce12")

ce13 = Graph("ExOG")
ce13.name(new = "ce13")

# CE to (~(matching_covered))->(has_residue_equals_alpha)
ce14 = Graph('[email protected]?')
ce14.name(new = "[email protected]?")

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

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

# CE to independence_number(x) >= 1/2*cvetkovic(x)
ce17 = Graph("[email protected]@[email protected]?C?S")
ce17.name(new = "ce17")

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

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

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

# CE to independence_number(x) <= median_degree(x)^2 + card_periphery(x)
ce21 = Graph('FiQ?_')
ce21.name(new = "ce21")

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

# CE to independence_number(x) <= inverse_degree(x) + order_automorphism_group(x) + 1
ce23 = Graph("HkIU|eA")
ce23.name(new = "ce23")

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

# CE to independence_number(x) <= floor(e^(maximum(max_even_minus_even_horizontal(x), fiedler(x))))
ce25 = Graph('[email protected]')
ce25.name(new = "ce25")

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

# CE to independence_number(x) <= floor(average_distance(x)) + maximum(max_even_minus_even_horizontal(x), brinkmann_steffen(x))
ce27 = Graph("K_GBXSysCE_")
ce27.name(new = "ce27")

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

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

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

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

# CE to independence_number(x) >= order(x)/szekeres_wilf(x)
ce32 = Graph('H?@Cbg')
ce32.name(new = "ce32")

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

# CE to independence_number(x) <= card_center(x) + maximum(diameter(x), card_periphery(x))
ce34 = Graph('H?PA_F_')
ce34.name(new = "ce34")

# CE to independence_number(x) <= card_center(x) + maximum(diameter(x), card_periphery(x))ce35 = Graph("")
ce35 = Graph("HDcgGO")
ce35.name(new = "ce35")

# CE to independence_number(x) >= max_degree(x) - order_automorphism_group(x)
ce36 = Graph('ETzw')
ce36.name(new = "ce36")

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

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

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

# CE to independence_number(x) <= floor(inverse_degree(x)) + order_automorphism_group(x) + 1
ce40 = Graph('Htji~Ei')
ce40.name(new = "ce40")

# CE to independence_number(x) <= card_center(x) + maximum(residue(x), card_periphery(x))
ce42 = Graph('GP[KGC')
ce42.name(new = "ce42")

# CE to independence_number(x) <= maximum(girth(x), (barrus_bound(x) - order_automorphism_group(x))^2)
ce43 = Graph("Exi?")
ce43.name(new = "ce43")

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

# CE to independence_number(x) <= maximum(max_even_minus_even_horizontal(x), radius(x)*szekeres_wilf(x))
ce45 = Graph("FWKH?")
ce45.name(new = "ce45")

# CE to independence_number(x) <= maximum(card_periphery(x), radius(x)*szekeres_wilf(x))
ce46 = Graph('FI?')
ce46.name(new = "ce46")

# CE to independence_number(x) <= maximum(card_periphery(x), diameter(x) + inverse_degree(x))
ce47 = Graph("KVOzWAxewcaE")
ce47.name(new = "ce47")

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

# CE to independence_number(x) >= sqrt(card_positive_eigenvalues(x))
ce49 = Graph("K^~lmrvv{~~Z")
ce49.name(new = "ce49")

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

# CE to independence_number(x) >= matching_number(x) - order_automorphism_group(x) - 1
ce51 = Graph("Ivq~j^~vw")
ce51.name(new = "ce51")

# CE to independence_number(x) >= order(x)/szekeres_wilf(x)
ce52 = Graph('H?QaOiG')
ce52.name(new = "ce52")

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

# CE to independence_number(x) >= -average_distance(x) + ceil(lovasz_theta(x))
ce54 = Graph('lckMIWzcWDsSQ_xTlFX?AoCbEC?f^xwGHOA_q?mPDDvicEWP[email protected][email protected]}CiG?HCsm_JO?QhI?ARLAcdBAaOh_QMG?D_o_FvQgHGHD?sKLEAR^[email protected][email protected]DkC')
ce54.name(new = "ce54")

# CE to independence_number(x) >= -card_periphery(x) + matching_number(x)
ce55 = Graph("I~~~~~~zw")
ce55.name(new = "ce55")

# CE to independence_number(x) >= lovasz_theta(x)/edge_con(x)
ce56 = Graph('HsaGpOe')
ce56.name(new = "ce56")

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

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

# CE to independence_number(x) >= floor(tan(barrus_bound(x) - 1))
ce59 = Graph("[email protected]??_?N??F??B_??w?")
ce59.name(new = "ce59")

# CE to independence_number(x) >= -1/2*diameter(x) + lovasz_theta(x)
ce60 = Graph('wSh[?GCfclJm?hmgA^We?Q_KIXbf\@SgDNxpwHTQIsIB?MIDZukArBAeXEvqDLbHCwf{fD?bKSVLklQHspD[email protected]?yW\YOCeaqmOfsZ?rmOSM?}HwPCIAYLdFx?o[B?]ZYb~IK~Zol~Ux[B]tYUE_gnVyHRQ?{cXG?k\[email protected]?Q?QbSKM@[BVCKDcMxF|ADGGMBWANV_IKw??DRkY\KOCW??P_?ExJDSAg')
ce60.name(new = "ce60")

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

# CE to independence_number(x) >= minimum(floor(lovasz_theta(x)), tan(spanning_trees_count(x)))
ce62 = Graph("qWGh???BLQcAH[email protected][email protected]@WOEBgRCoSE[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")

# CE to independence_number(x) >= diameter(x)/different_degrees(x)
ce63 = Graph("[email protected]")
ce63.name(new = "ce63")

# CE to independence_number(x) >= -max_common_neighbors(x) + min_degree(x)
ce64 = Graph('szvym|h~RMQLTNNiZzsgQynDR\p~~rTZXi~nkVvKolVJfP}TVEN}Thj~tv^KJ}D~VqqsNy|NY|ybklZLnz~TfyG')
ce64.name(new = "ce64")

# CE to independence_number(x) >= -10^different_degrees(x) + matching_number(x)
ce65 = Graph("W~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~")
ce65.name(new = "ce65")

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

# CE to independence_number(x) <= maximum(cycle_space_dimension(x), floor(lovasz_theta(x)))
ce67 = Graph("G??EDw")
ce67.name(new = "ce67")

# CE to independence_number(x) >= minimum(card_positive_eigenvalues(x), 2*card_zero_eigenvalues(x))
ce68 = Graph('HzzP|~]')
ce68.name(new = "ce68")

# CE to independence_number(x) <= maximum(max_degree(x), radius(x)^card_periphery(x))
ce69 = Graph("F?BvO")
ce69.name(new = "ce69")

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

# CE to independence_number(x) <= maximum(matching_number(x), critical_independence_number(x))
ce71 = Graph('ECYW')
ce71.name(new = "ce71")

# CE to independence_number(x)>=-1/2*x.diameter() + x.lovasz_theta()
ce72 = Graph('fdSYkICGVs_m_TPsFmj_|[email protected]@_[@[email protected]TC{[email protected]?HBDS[R?CdG\[email protected]?GNHGXgYpVGCoJdOKBJQAsG|ICE_BeMQGOwKqSd\W?CRg')
ce72.name(new = "ce72")

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

# CE to independence_number(x) >= minimum(diameter(x), lovasz_theta(x))
ce74 = Graph("FCQb_")
ce74.name(new = "ce74")

# CE to independence_number(x) >= minimum(girth(x), floor(lovasz_theta(x)))
ce75 = Graph('E?Bw')
ce75.name(new = "ce75")

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

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

# CE to independence_number(x) <= maximum(max_degree(x), radius(x)^card_periphery(x))
ce78 = Graph("G_aCp[")
ce78.name(new = "ce78")

# CE to independence_number(x) <= residue(x)^2
ce79 = Graph('J?B|~fpwsw_')
ce79.name(new = "ce79")

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

# CE to independence_number(x) <= diameter(x)^card_periphery(x)
ce81 = Graph('P?????????^~v~V~rzyZ~du{')
ce81.name(new = "ce81")

# CE to independence_number(x) <= radius(x)*residue(x) + girth(x)
ce82 = Graph('O????B~~^Zx^wnc~ENqxY')
ce82.name(new = "ce82")

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

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

# CE to independence_number(x) <= girth(x)^ceil(laplacian_energy(x))
ce85 = Graph('[email protected]X?hB_?QKEo_opC?|[email protected]?CBIlqf_GQ][email protected][email protected]?CCA?OG?')
ce85.name(new = "ce85")

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

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

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

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

# 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{wNsn}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")

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

# 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}BtjyV~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")

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

# CE to independence_number(x) >= minimum(lovasz_theta(x), max_degree(x)/card_center(x))
ce112 = Graph("flthktLhme|L|L]efhg|LbstFhhFhgbssG|LFhiC]ecG|LCG|LaC]ewFhnCG|L{ObstwFhlwFhi{ObssnCG|LdwFhmVaC]eknCG|LknCG|L??????_?????G")
ce112.name(new = "ce112")

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

# 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}lpLX{L?")
ce132.name(new = "ce132")

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

# 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|UhPZHlzsmizxCPTiNL[Mv|kbKUI}^r}oiAdMLE\^rga{v][email protected]]Hb}wupjLhYg|Rn|b[iLNp}Oudo~r_oFEjTzvw')
ce134.name(new = "ce134")

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

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

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

# CE to independence_number(x) >= minimum(floor(lovasz_theta(x)), tan(randic(x)))
paley_53e = graphs.PaleyGraph(53)
paley_53e.name(new = "paley_53e")

paley_101 = graphs.PaleyGraph(101)
paley_101.name(new = "paley_101")

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

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

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

edge_critical_5=graphs.CycleGraph(5)
edge_critical_5.name(new="edge_critical_5")

# CE to independence_number(x) >= min(e - n + 1, diameter(x))
heather = graphs.CompleteGraph(4)
heather.name(new="heather")

#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.name(new="ryan3")

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

fork = graphs.PathGraph(4)
fork.name(new="fork")

# 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.name(new="edge_critical_11_1")

#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.name(new="edge_critical_11_2")

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

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

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

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

# 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.name(new = "k4e2split")

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

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

flower_with_3_petals = flower(3)
flower_with_3_petals.name(new = "flower_with_3_petals")

flower_with_4_petals = flower(4)
flower_with_4_petals.name(new = "flower_with_4_petals")

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

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

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

"""
From Willis's thesis, page 7

2
sage: average_distance(willis_page7)
1.467
"""
willis_page7 = Graph("ELRW")
willis_page7.name(new = "willis_page7")

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

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

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

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

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

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