Sharedgt.sageOpen in CoCalc
#GRAPH UTILITIES

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

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

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

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

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

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

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

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

There are two alpha critical graphs on 5 vertices::

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

There are two alpha critical graphs on 6 vertices::

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

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

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

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

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

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

#ALPHA APPROXIMATIONS

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

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

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

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

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

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

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

LP.solve()

#return LP

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

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

for (i,j) in g.edges(labels = False):
#print (i,j)
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 g.has_edge(u,v) and g.has_edge(u,v) and pos[u] > pos[w]]
for u in S:
s = Set([u,v,w])
triangles.append(s)
return triangles

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

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

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

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

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

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

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

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

sage: ml10
sage: ml10.order()
20
sage: ml10.degree()
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
sage: ml10.is_apex()
True
sage: ml10.is_vertex_transitive()
True
"""
g = graphs.CycleGraph(2*k)
for i in range(k):
return g

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

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

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

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

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

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

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

EXAMPLES:

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

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

#TESTING

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

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

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

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

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

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

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

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

for i in sage_efficient_invariants:
for i in sage_intractable_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 the median of the list of vertex degrees.

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

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

Return 0 if the graph has no edges.

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

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.

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

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

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

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

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

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

return len(seq)

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

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

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

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

return a

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

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

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

for v in g.vertices():

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

return p.solve()

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

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

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

for v in g.vertices():

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

return p.solve()

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

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

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

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

return zero + min([positive, negative])

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

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

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

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

#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 range(1,g.order()):
summation += (i*(i+1))/2
return summation * 2
else:
V = g.vertices()
D = g.distance_all_pairs()
return sum([D[v][w] for v in V for w in V if v != w])

def harmonic_index(g):
sum = 0
for (u,v) in g.edges(labels = false):
sum += (2 / (g.degree(u) + g.degree(v)))
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

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

def max_edge_clustering_centrality(g):
"""
sage: max_edge_clustering_centrality(p3)
2
sage: max_edge_clustering_centrality(paw)
3
"""
return max(edge_clustering_centrality(g))

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

# Define that for copmlete graphs (i.e. nothing to minimize over later), return n, which is trivial upper bound.
all_dist = g.distance_all_pairs()
nonadj = [(v,w) for v in g for w in g if all_dist[v][w] > 1]
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 all_dist[v][w] == 2]
if not dist2:
return g.order()
else:
return min( len(union(g.neighbors(v), g.neighbors(w))) for (v, w) in dist2)

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

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

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

#####
# 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 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 range(1, upper+1):
for s in SetV.subsets(i):
count = 0
for u in s:
for w in SetV.difference(s):
for e in g.edges(labels=false):
if Set([u,w]) == Set(e):
count += 1
temp = count/i
if temp < best:
best = temp
return best

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):
"""
Evalutes whether graph g has a vertex adjacent to all others.

EXAMPLES:

sage: has_star_center(flower_with_3_petals)
True

sage: has_star_center(c4)
False

Edge cases ::

sage: has_star_center(Graph(1))
True

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

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

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

EXAMPLES:

sage: is_complement_of_chordal(p4)
True

sage: is_complement_of_chordal(Graph(4))
True

sage: is_complement_of_chordal(p5)
False

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

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

sage: is_complement_of_chordal(Graph(3))
True

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

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

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

EXAMPLES:

sage: pairs_have_unique_common_neighbor(flower(5))
True

sage: pairs_have_unique_common_neighbor(k3)
True

sage: pairs_have_unique_common_neighbor(k4)
False

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

Vacuous cases ::

sage: pairs_have_unique_common_neighbor(Graph(1))
True

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

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

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

EXAMPLES:

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

sage: is_distance_transitive(graphs.PetersenGraph())
True

sage: is_distance_transitive(Graph(3))
True

sage: is_distance_transitive(graphs.ShrikhandeGraph())
False

This method accepts disconnected graphs. ::

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

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

Vacuous cases ::

sage: is_distance_transitive(Graph(0))
True

sage: is_distance_transitive(Graph(1))
True

sage: is_distance_transitive(Graph(2))
True

... WARNING ::

This method calls, via the automorphism group, the Gap package. This
"""
from itertools import combinations
dist_dict = g.distance_all_pairs()
auto_group = g.automorphism_group()

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

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

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

EXAMPLES:

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

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

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

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

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

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

EXAMPLES:

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

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

sage: is_ore(dart)
False

sage: is_ore(Graph(2))
False

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

Vacous cases ::

sage: is_ore(Graph(0))
True

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

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

INPUT:

- g -- graph

EXAMPLES:

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

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

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

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

sage: is_haggkvist_nicoghossian(Graph(1))
False

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

REFERENCES:

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

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

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

OUTPUT:

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

EXAMPLES:

sage: is_genghua_fan(graphs.DiamondGraph())
True

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

sage: is_genghua_fan(graphs.ButterflyGraph())
False

sage: is_genghua_fan(Graph(1))
False

REFERENCES:

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

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

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

EXAMPLES:

sage: is_planar_transitive(graphs.HexahedralGraph())
True

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

sage: is_planar_transitive(graphs.FranklinGraph())
False

sage: is_planar_transitive(graphs.BullGraph())
False

Vacuous cases ::

sage: is_planar_transitive(Graph(1))
True

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

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

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

OUTPUT:

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

EXAMPLES:

sage: is_generalized_dirac(graphs.HouseGraph())
True

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

sage: is_generalized_dirac(graphs.DiamondGraph())
False

sage: is_generalized_dirac(Graph(1))
False

REFERENCES:

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

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

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

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

INPUT:

- g -- graph

OUTPUT:

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

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

EXAMPLES:

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

sage: is_van_den_heuvel(graphs.PetersenGraph())
False

REFERENCES:

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

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

TESTS::

sage: is_van_den_heuvel(Graph(0))
False

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

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

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

return True

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

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

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

EXAMPLES:

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

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

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

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

sage: is_two_connected(Graph(3))
False

Edge cases ::

sage: is_two_connected(Graph(0))
False

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

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

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

EXAMPLES:

sage: is_three_connected(graphs.PetersenGraph())
True

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

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

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

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

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

sage: is_three_connected(Graph(4))
False

Edge cases ::

sage: is_three_connected(Graph(0))
False

sage: is_three_connected(Graph(1))
False

.. WARNING::

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

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

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

EXAMPLES:

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

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

sage: is_four_connected(Graph(5))
False

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

Edge cases ::

sage: is_four_connected(Graph(0))
False

sage: is_four_connected(Graph(1))
False

.. WARNING::

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

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

OUTPUT:

Let g be of order n.

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

EXAMPLES:

sage: is_lindquester(graphs.HouseGraph())
True

sage: is_lindquester(graphs.OctahedralGraph())
True

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

sage: is_lindquester(graphs.DiamondGraph())
False

REFERENCES:

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

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

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

OUTPUT:

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

EXAMPLES:

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

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

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

sage: is_complete(Graph(0))
True

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

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

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

EXAMPLES:

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

sage: has_c4(graphs.HouseGraph())
True

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

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

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

EXAMPLES:

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

sage: is_c4_free(graphs.HouseGraph())
False

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

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

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

OUTPUT:

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

EXAMPLES:

sage: has_paw(paw)
True

sage: has_paw(graphs.BullGraph())
True

sage: has_paw(graphs.ClawGraph())
False

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

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

OUTPUT:

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

EXAMPLES:

sage: is_paw_free(paw)
False

sage: is_paw_free(graphs.BullGraph())
False

sage: is_paw_free(graphs.ClawGraph())
True

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

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

OUTPUT:

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

EXAMPLES:

sage: has_dart(dart)
True

sage: has_dart(umbrella_4)
True

sage: has_dart(graphs.DiamondGraph())
False

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

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

OUTPUT:

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

EXAMPLES:

sage: is_dart_free(dart)
False

sage: is_dart_free(umbrella_4)
False

sage: is_dart_free(graphs.DiamondGraph())
True

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

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

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

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

EXAMPLES:

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

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

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

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

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

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

EXAMPLES:

sage: has_kite(kite_with_tail)
True

sage: has_kite(graphs.KrackhardtKiteGraph())
True

sage: has_kite(graphs.DiamondGraph())
False

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

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

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

EXAMPLES:

sage: is_kite_free(kite_with_tail)
False

sage: is_kite_free(graphs.KrackhardtKiteGraph())
False

sage: is_kite_free(graphs.DiamondGraph())
True

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

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

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

EXAMPLES:

sage: has_claw(graphs.ClawGraph())
True

sage: has_claw(graphs.PetersenGraph())
True

sage: has_claw(graphs.BullGraph())
False

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

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

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

EXAMPLES:

sage: is_claw_free(graphs.ClawGraph())
False

sage: is_claw_free(graphs.PetersenGraph())
False

sage: is_claw_free(graphs.BullGraph())
True

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

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

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

EXAMPLES:

sage: has_H(double_fork)
True

sage: has_H(graphs.PetersenGraph())
True

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

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

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

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

EXAMPLES:

sage: is_H_free(double_fork)
False

sage: is_H_free(graphs.PetersenGraph())
False

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

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

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

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

EXAMPLES:

sage: has_fork(star_1_1_3)
True

sage: has_fork(graphs.PetersenGraph())
True

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

sage: has_fork(graphs.HouseGraph())
False

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

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

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

EXAMPLES:

sage: is_fork_free(star_1_1_3)
False

sage: is_fork_free(graphs.PetersenGraph())
False

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

sage: is_fork_free(graphs.HouseGraph())
True

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

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

K_4 is the complete graph on 4 vertices.

EXAMPLES:

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

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

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

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

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

K_4 is the complete graph on 4 vertices.

EXAMPLES:

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

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

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

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

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

EXAMPLE:

sage: is_double_clique(p4)
True

sage: is_double_clique(graphs.ButterflyGraph())
True

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

sage: is_double_clique(graphs.ClawGraph())
False

sage: is_double_clique(Graph(3))
False

Edge cases ::

sage: is_double_clique(Graph(0))
True

sage: is_double_clique(Graph(1))
True

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

"""
Evaluates whether the radius of graph g equals its diameter.

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

Both radius and diameter are undefined for the empty graph.

EXAMPLES:

True

True

True

False

False
"""

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

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

Residue is undefined on the empty graph.

EXAMPLES:

sage: has_residue_equals_alpha(graphs.HouseGraph())
True

sage: has_residue_equals_alpha(graphs.ClawGraph())
True

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

sage: has_residue_equals_alpha(Graph(1))
True

sage: has_residue_equals_alpha(graphs.PetersenGraph())
False

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

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

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

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

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

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

sage: is_not_forest(graphs.HouseGraph())
True

Edge cases ::

sage: is_not_forest(Graph(1))
False

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

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

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

EXAMPLES:

sage: has_empty_KE_part(graphs.PetersenGraph())
True

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

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

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

Edge cases ::

sage: has_empty_KE_part(Graph(1))
False

sage: has_empty_KE_part(Graph(0))
True

ALGORITHM:

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

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

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

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

Finally, use the Gallai identities to show matching

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

REFERENCES:

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

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

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

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

Max degree is undefined for the empty graph.

EXAMPLES:

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

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

sage: is_class1(Graph(1))
True

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

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

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

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

Max degree is undefined for the empty graph.

EXAMPLES:

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

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

sage: is_class2(Graph(1))
False

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

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

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

EXAMPLES:

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

sage: is_cubic(graphs.PetersenGraph())
True

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

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

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

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

Diameter is undefined for the empty graph.

EXAMPLES:

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

sage: is_anti_tutte(graphs.PetersenGraph())
True

sage: is_anti_tutte(Graph(1))

sage: is_anti_tutte(graphs.TutteGraph())
False

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

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

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

Radius is undefined for the empty graph.

EXAMPLES:

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

sage: is_anti_tutte2(graphs.PetersenGraph())
True

sage: is_anti_tutte2(graphs.TutteGraph())
False

sage: is_anti_tutte2(graphs.TutteCoxeterGraph())
False

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

"""
Evaluates whether the diameter of graph g is equal to twice its radius.

Diameter and radius are undefined for the empty graph.

EXAMPLES:

True

True

False

False

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

True

Disconnected graphs have both diameter and radius equal infinity.

True
"""

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

Diameter is undefined for the empty graph.

EXAMPLES:

sage: diameter_equals_two(graphs.ClawGraph())
True

sage: diameter_equals_two(graphs.HouseGraph())
True

sage: diameter_equals_two(graphs.KrackhardtKiteGraph())
False

sage: diameter_equals_two(graphs.BullGraph())
False

Disconnected graphs have diameter equals infinity.

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

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

Examples:

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

sage: has_lovasz_theta_equals_alpha(double_fork)
True

sage: has_lovasz_theta_equals_alpha(graphs.PetersenGraph())
True

sage: has_lovasz_theta_equals_alpha(graphs.ClebschGraph())
False

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

True for all graphs with no edges ::

sage: has_lovasz_theta_equals_alpha(Graph(12))
True

Edge cases ::

sage: has_lovasz_theta_equals_alpha(Graph(0))
True

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

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

Examples:

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

sage: has_lovasz_theta_equals_cc(double_fork)
True

sage: has_lovasz_theta_equals_cc(graphs.PetersenGraph())
True

sage: has_lovasz_theta_equals_cc(Graph(12))
True

sage: has_lovasz_theta_equals_cc(graphs.ClebschGraph())
False

has_lovasz_theta_equals_alpha(graphs.BuckyBall())
False

Edge cases ::

sage: has_lovasz_theta_equals_cc(Graph(0))
True

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

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

OUTPUT:

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

EXAMPLES:

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

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

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

sage: is_chvatal_erdos(graphs.PetersenGraph())
False

sage: is_chvatal_erdos(graphs.ClawGraph())
False

sage: is_chvatal_erdos(graphs.DodecahedralGraph())
False

Edge cases ::

sage: is_chvatal_erdos(Graph(1))
False

sage: is_chvatal_erdos(Graph(0))
True

REFERENCES:

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

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

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

"""
Test if connected graph g has radius greater than num. of center verts.

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

EXAMPLES:

True

True

True

False

False

False
"""
return g.is_connected() and g.radius() > card_center(g)

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

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

EXAMPLES:

sage: avg_distance_greater_than_girth(graphs.TutteGraph())
True

sage: avg_distance_greater_than_girth(graphs.HarborthGraph())
True

sage: avg_distance_greater_than_girth(graphs.HortonGraph())
True

sage: avg_distance_greater_than_girth(graphs.BullGraph())
False

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

sage: avg_distance_greater_than_girth(Graph(2))
False

Acyclic graphs have girth equals infinity. ::

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

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

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

Some of these invariants are undefined on the empty graph.

EXAMPLES:

sage: chi_equals_min_theory(Graph(1))
True

sage: chi_equals_min_theory(graphs.PetersenGraph())
True

sage: chi_equals_min_theory(double_fork)
True

sage: chi_equals_min_theory(Graph(3))
False

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

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

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

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

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

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

EXAMPLES:

REFERENCES:

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

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

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

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

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

EXAMPLES:

REFERENCES:

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

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

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

EXAMPLES:

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

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

sage: is_traceable(graphs.PetersenGraph())
True

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

sage: is_traceable(Graph(3))
False

sage: is_traceable(graphs.ClawGraph())
False

sage: is_traceable(graphs.ButterflyGraph())
False

Edge cases ::

sage: is_traceable(Graph(0))
False

sage: is_traceable(Graph(1))
False

ALGORITHM:

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

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

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

Residue is undefined on the empty graph.

EXAMPLES:

sage: has_residue_equals_two(graphs.ButterflyGraph())
True

sage: has_residue_equals_two(graphs.IcosahedralGraph())
True

sage: has_residue_equals_two(graphs.OctahedralGraph())
True

sage: has_residue_equals_two(Graph(1))
False

sage: has_residue_equals_two(graphs.BullGraph())
False

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

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

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

OUTPUT:

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

EXAMPLES:

sage: is_chordal_or_not_perfect(graphs.DiamondGraph())
True

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

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

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

sage: is_chordal_or_not_perfect(graphs.HexahedralGraph())
False

Vacuously chordal cases ::

sage: is_chordal_or_not_perfect(Graph(0))
True

sage: is_chordal_or_not_perfect(Graph(1))
True

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

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

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

Residue is undefined on the empty graph.

EXAMPLES:

sage: has_alpha_residue_equal_two(graphs.DiamondGraph())
True

sage: has_alpha_residue_equal_two(Graph(2))
True

sage: has_alpha_residue_equal_two(graphs.OctahedralGraph())
True

sage: has_alpha_residue_equal_two(graphs.BullGraph())
False

sage: has_alpha_residue_equal_two(graphs.BidiakisCube())
False

sage: has_alpha_residue_equal_two(Graph(3))
False

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

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

EXAMPLES:

sage: alpha_leq_order_over_two(graphs.ButterflyGraph())
True

sage: alpha_leq_order_over_two(graphs.DiamondGraph())
True

sage: alpha_leq_order_over_two(graphs.CoxeterGraph())
True

sage: alpha_leq_order_over_two(Graph(4))
False

sage: alpha_leq_order_over_two(graphs.BullGraph())
False

Edge cases ::

sage: alpha_leq_order_over_two(Graph(0))
True

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

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

Undefined for the empty graph.

EXAMPLES:

sage: order_leq_twice_max_degree(graphs.BullGraph())
True

sage: order_leq_twice_max_degree(graphs.ThomsenGraph())
True

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

sage: order_leq_twice_max_degree(graphs.BidiakisCube())
False

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

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

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

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

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

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

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

EXAMPLES:

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

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

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

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

sage: is_chromatic_index_critical(graphs.PetersenGraph())
False

sage: is_chromatic_index_critical(graphs.FlowerSnark())
False

Non-trivially disconnected graphs ::

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

Class 1 graphs ::

sage: is_chromatic_index_critical(Graph(1))
False

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

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

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

ALGORITHM:

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

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

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

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

REFERENCES:

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

if chi == max_degree(g):
return False

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

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

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

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

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

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

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

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

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

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

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

#returns twin pair (v,w) if one exists, else returns None
def find_twin(g):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

# g is bad if a block is isomorphic to k3, c5, k4*, c5*
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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

def has_F(g):
"""
Let F be a triangle with 3 pendants. True if g has an induced F.
"""
F = graphs.CycleGraph(3)
return g.subgraph_search(F, induced = True) != None

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

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

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

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

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

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

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

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

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

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

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

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

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

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

EXAMPLES:

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

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

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

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

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

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

sage: is_maximal_triangle_free(graphs.HouseGraph())
False

Edge cases ::

sage: is_maximal_triangle_free(Graph(0))
False

sage: is_maximal_triangle_free(Graph(1))
False

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

def is_locally_two_connected(g):
"""

ALGORITHM:

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

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

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

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

return equality_checker

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

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

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

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

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

equality_checker.__doc__ = documentation

return equality_checker

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

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

return comparator

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

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

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

localised_function.__doc__ = documentation

return localised_function

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

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

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

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

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

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

removed_properties = [is_pebbling_class0]

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

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

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

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

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

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

#############################################################################
# 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) - g.triangles_count()

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

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

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*d + 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) - g.triangles_count()

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

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) # Causes memory error when doctesting. Waiting for fix in Sage.
# janko_kharaghani1800.name(new = "Janko-Kharagani 1800")

for graph in sage_graphs + [mathon_strongly_regular0, mathon_strongly_regular1, mathon_strongly_regular2, janko_kharaghani936]:

# 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 * x.chromatic_number() + 2 * residue(x)
# has alpha=25,chi=2,residue=10
ryan2=graphs.CirculantGraph(50,[1,3])
ryan2.name(new="circulant_50_1_3")

# From Ryan Pepper
# CE to independence_number(x) >= diameter(x) - 1 for regular graphs

# p10 joined to 2 points of k4
# CE to chromatic_number <= avg_degree + 1
p10k4=Graph('[email protected][email protected]_B?B_')
p10k4.name(new="p10k4")

# 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]????????_???GHC???CG?[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][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")
ce84 = Graph('[email protected][email protected][email protected][email protected][email protected]?S?O??[email protected]