Day5.sagews

#this the conjecturing program
load("conjecturing.py")

#this is a list of pre-coded graphs, properties, and invariants
load("gt-nb.sage")

loaded utilities loaded invariants loaded properties loaded theorems loaded graphs Remember to load DIMACS and Sloane graphs if you want them

k3 = graphs.CompleteGraph(3)
#[(is_clique)->(is_hamiltonian)] is TRUE
k3_4 = graphs.CompleteBipartiteGraph(3,4)
k5_5 = graphs.CompleteBipartiteGraph(5,5)
#(is_cycle)->(is_hamiltonian) is TRUE
k2 = graphs.CompleteGraph(2)
EH = graphs.EllinghamHorton54Graph()
#CLAIM: ((is_strongly_regular)&(is_bipartite))->(is_hamiltonian) is true for n>2
#NB presented a proof: we need to write this up!
pete = graphs.PetersenGraph()
c5 = graphs.CycleGraph(5)
fish = Graph([(0,1),(1,2),(2,3),(3,4),(4,5),(5,2),(2,0)])
c5_tail = graphs.CycleGraph(5)
#c5_tail.add_vertex()
c5_tail.add_edge(0,5)
bow_tie = Graph(5)
bow_tie.add_edges([(0,1),(1,2),(2,3),(3,4),(4,2),(2,0)])
c7 = graphs.CycleGraph(7)
c7_chord = graphs.CycleGraph(7)
c7_chord.add_edge(0,2)
glasses = Graph(7)
glasses.add_edges([(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,3),(3,0)])
p3 = graphs.PathGraph(3)
k5 = graphs.CompleteGraph(5)

triangle_with_tail = graphs.CompleteGraph(3)
triangle_with_tail.add_edge(0,3)
blanusa2 = graphs.BlanusaSecondSnarkGraph()
duplex = Graph("Iv?GOKFY?")
heawood = graphs.HeawoodGraph()
frucht = graphs.FruchtGraph()
nb1 = Graph("Edj_")
tutte = graphs.TutteGraph()

#Run 4 of Day 4 - RERUN

matching_robust = lambda g: matching_covered(g)

current_graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail,triangle_with_tail]
current_graph_objects.append(blanusa2)
current_graph_objects.append(frucht)
current_graph_objects.append(heawood)
current_graph_objects.append(duplex)
current_graph_objects.append(nb1)
current_graph_objects.append(tutte)

#properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian, Graph.is_triangle_free, Graph.is_distance_regular, Graph.is_perfect, Graph.is_planar]

#the properties list used in the conjecturing program will be the on from gt.sage

property_of_interest = properties.index(Graph.is_hamiltonian)

matching_robust = lambda g: matching_covered(g)
theorems = [matching_robust, is_van_den_heuvel]
#we're started with no knowledge of necessary conditions for hamiltonicity

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems, sufficient=False)
for c in conjs:
    print c

(is_hamiltonian)->((is_perfect)->(has_radius_equal_diameter)) (is_hamiltonian)->((is_independence_irreducible)|(is_distance_regular)) (is_hamiltonian)->((is_perfect)|(is_planar)) (is_hamiltonian)->((is_triangle_free)->(is_distance_regular))

nb1 = Graph("Edj_")
nb1.show()

len(current_graph_objects)

20

for g in current_graph_objects:
    print g, g.is_hamiltonian()
    g.show()

Complete graph True

Petersen graph False

Cycle graph True

Complete bipartite graph True

Complete bipartite graph False

Ellingham-Horton 54-graph False

Cycle graph True

Graph on 5 vertices False

Complete graph True

Path graph False

Graph on 7 vertices False

Graph on 6 vertices False

Cycle graph False

Complete graph False

Blanusa Second Snark Graph False

Frucht graph True

Heawood graph True

Graph on 10 vertices False

Graph on 6 vertices False

Tutte Graph False

for g in current_graph_objects:
    if not g.is_hamiltonian():
        if matching_robust(g):
            print g
            g.show()

Petersen graph

Complete bipartite graph

Ellingham-Horton 54-graph

Graph on 5 vertices

Path graph

Graph on 7 vertices

Blanusa Second Snark Graph

Tutte Graph

for g in current_graph_objects:
    if not g.is_hamiltonian():
        if is_van_den_heuvel(g):
            print g
            g.show()

Ellingham-Horton 54-graph

Blanusa Second Snark Graph

Graph on 6 vertices

Tutte Graph

test = lambda g: g.is_perfect() or g.is_planar()
for g in current_graph_objects:
    if not test(g):
        print g
        g.show()

Petersen graph

Blanusa Second Snark Graph

robertson = graphs.RobertsonGraph()
robertson.show()

conjs[0]

(is_hamiltonian)->((is_perfect)->(has_radius_equal_diameter))

conjs[0](robertson)

True

conjs[1](robertson)

True

conjs[2](robertson)

False

conjs[2]

(is_hamiltonian)->((is_perfect)|(is_planar))

#NOTE: add Robertson graph to get new conjectures not including: 
#is_hamiltonian)->((is_perfect)|(is_planar))

hoffman = graphs.HoffmanGraph()
hoffman.is_hamiltonian()
hoffman.show()

True

#IS hoffman a CE to the open necessary condition conjectures?
conjs[0]
conjs[0](hoffman)

(is_hamiltonian)->((is_perfect)->(has_radius_equal_diameter)) False

#Run 1 of Day 5
#add melissas counterexamples: robertson & hoffman graphs
#hoffman graph is a CE to:
#hamiltonian => ((is_perfect)->(has_radius_equal_diameter))
#robertson is a CE to:
#(is_hamiltonian)->((is_perfect)|(is_planar)

matching_robust = lambda g: matching_covered(g)

current_graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail,triangle_with_tail]
current_graph_objects.append(blanusa2)
current_graph_objects.append(frucht)
current_graph_objects.append(heawood)
current_graph_objects.append(duplex)
current_graph_objects.append(nb1)
current_graph_objects.append(tutte)

hoffman = graphs.HoffmanGraph()
current_graph_objects.append(hoffman)
robertson = graphs.RobertsonGraph()
current_graph_objects.append(robertson)

#properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian, Graph.is_triangle_free, Graph.is_distance_regular, Graph.is_perfect, Graph.is_planar]

#the properties list used in the conjecturing program will be the on from gt.sage

property_of_interest = properties.index(Graph.is_hamiltonian)

matching_robust = lambda g: matching_covered(g)
theorems = [matching_robust, is_van_den_heuvel]
#we're started with no knowledge of necessary conditions for hamiltonicity

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems, sufficient=False)
for c in conjs:
    print c

(is_hamiltonian)->((is_anti_tutte)&(is_van_den_heuvel)) (is_hamiltonian)->((is_anti_tutte)&(matching_covered)) (is_hamiltonian)->((has_perfect_matching)->(is_class1))

#folkman is CE to conjs[0] and conjs[1]

folkman = graphs.FolkmanGraph()
folkman.show()

conjs[0]

(is_hamiltonian)->((is_anti_tutte)&(is_van_den_heuvel))

conjs[1]

(is_hamiltonian)->((is_anti_tutte)&(matching_covered))

conjs[2]

(is_hamiltonian)->((has_perfect_matching)->(is_class1))

conjs[0](folkman)

False

conjs[1](folkman)

False

conjs[2](folkman)

True

house = graphs.HouseGraph()

house.show()

conjs[2](house)

True

subdivided_k5 = graphs.CompleteGraph(5)
subdivided_k5.subdivide_edge((0,1),1)
subdivided_k5.show()
subdivided_k5.chromatic_index()

5

conjs[2](subdivided_k5)

False

#Run 2 of Day 5
#folkman, house, and subdivided_k5 graphs

matching_robust = lambda g: matching_covered(g)

current_graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail,triangle_with_tail]
current_graph_objects.append(blanusa2)
current_graph_objects.append(frucht)
current_graph_objects.append(heawood)
current_graph_objects.append(duplex)
current_graph_objects.append(nb1)
current_graph_objects.append(tutte)

hoffman = graphs.HoffmanGraph()
current_graph_objects.append(hoffman)
robertson = graphs.RobertsonGraph()
current_graph_objects.append(robertson)

current_graph_objects.append(folkman)
current_graph_objects.append(house)
current_graph_objects.append(subdivided_k5)

#properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian, Graph.is_triangle_free, Graph.is_distance_regular, Graph.is_perfect, Graph.is_planar]

#the properties list used in the conjecturing program will be the on from gt.sage

property_of_interest = properties.index(Graph.is_hamiltonian)

matching_robust = lambda g: matching_covered(g)
theorems = [matching_robust, is_van_den_heuvel]
#we're started with no knowledge of necessary conditions for hamiltonicity

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems, sufficient=False)
for c in conjs:
    print c

(is_hamiltonian)->(((is_regular)->(is_planar))->(is_anti_tutte2)) (is_hamiltonian)->((~(is_independence_irreducible))^(is_anti_tutte2)) (is_hamiltonian)->((is_cubic)->(is_class1)) (is_hamiltonian)->((has_c4)|(has_radius_equal_diameter))

theorem_n1 = lambda g: not is_cubic(g) or is_class1(g)
theorem_n1(c7)
theorem_n1(pete)

True False

#Dr H sketched a proof of: (hamiltonian)->((is_cubic)->(is_class1)
#can the students recreate this proof?
#Run 3 of Day 5
#add the theorem

matching_robust = lambda g: matching_covered(g)

current_graph_objects = [k3,pete,c5,k5_5,k3_4,EH,c7_chord,bow_tie,k5,p3,glasses,fish,c5_tail,triangle_with_tail]
current_graph_objects.append(blanusa2)
current_graph_objects.append(frucht)
current_graph_objects.append(heawood)
current_graph_objects.append(duplex)
current_graph_objects.append(nb1)
current_graph_objects.append(tutte)

hoffman = graphs.HoffmanGraph()
current_graph_objects.append(hoffman)
robertson = graphs.RobertsonGraph()
current_graph_objects.append(robertson)

current_graph_objects.append(folkman)
current_graph_objects.append(house)
current_graph_objects.append(subdivided_k5)

#properties = [Graph.is_hamiltonian, Graph.is_clique, Graph.is_regular,Graph.is_cycle,Graph.is_bipartite,Graph.is_chordal,Graph.is_strongly_regular,Graph.is_eulerian, Graph.is_triangle_free, Graph.is_distance_regular, Graph.is_perfect, Graph.is_planar]

#the properties list used in the conjecturing program will be the on from gt.sage

property_of_interest = properties.index(Graph.is_hamiltonian)

matching_robust = lambda g: matching_covered(g)
theorem_n1 = lambda g: not is_cubic(g) or is_class1(g)

theorems = [matching_robust, is_van_den_heuvel, theorem_n1]
#we're started with no knowledge of necessary conditions for hamiltonicity

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems, sufficient=False)
for c in conjs:
    print c

for g in current_graph_objects:
    if not g.is_hamiltonian() and theorem_n1(g):
        print g
        g.show()

Complete bipartite graph

Ellingham-Horton 54-graph

Graph on 5 vertices

Path graph

Graph on 7 vertices

Graph on 6 vertices

Cycle graph

Complete graph

Graph on 6 vertices

Tutte Graph

theorem_n1(blanusa2)

False

blanusa2.is_hamiltonian()

False

matching_robust(blanusa2)

True

is_van_den_heuvel(blanusa2)

True