CoCalc -- day10.sagews

¹¹⁷ views

load("conjecturing.py")
load("gt.sage")

loaded utilities
loaded invariants
loaded properties
loaded theorems
loaded graphs

Remember to load DIMACS and Sloane graphs if you want them

load("gt_precomputed_database.sage")
precomputed = precomputed_properties_for_conjecture()

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()
pete = graphs.PetersenGraph()

robertson = graphs.RobertsonGraph()
hoffman = graphs.HoffmanGraph()
folkman = graphs.FolkmanGraph()
house = graphs.HouseGraph()

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

grid_2_3=graphs.Grid2dGraph(2,3)
grid_3_3=graphs.Grid2dGraph(3,3)
grid_3_3_3 = graphs.GridGraph([3,3,3])
k_4_6 = graphs.CompleteBipartiteGraph(4,6)
k3_4_edge=graphs.CompleteBipartiteGraph(3,4)
k3_4_edge.add_edge(0,1)

c5_chord_tail = graphs.CycleGraph(5)
c5_chord_tail.add_edge(0,2)
c5_chord_tail.add_vertex()
c5_chord_tail.add_edge(1,5)

ham1 = Graph("I~EGYCxyG")
ham2 = Graph("IjCKY{Tvg")
ham3 = Graph("Shk{\LP[mZnPDR^LaE{qz?GCIhgCcmL?C")

c8_chorded = graphs.CycleGraph(8)
c8_chorded.add_edge(0,3)
c8_chorded.add_edge(4,7)

def kite_necklace(k):
    #returns k kites joined head to tail
    if k==1:
        return Graph('DJk')
    g = graphs.CycleGraph(2*k)
    for i in [0..k-1]:
        g.subdivide_edge((0+2*i,1+2*i),1)
        g.add_edge(0+2*i,1+2*i)
        g.subdivide_edge((0+2*i,1+2*i),1)
        g.add_edge(2*k+2*i,2*k+2*i+1)
    return g

umbrella_4 = Graph("Ep{G")

5
5

#Run 3 of Day 9, 
#RERUN, necessary condition conjectures

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)
current_graph_objects.append(hoffman)
current_graph_objects.append(robertson)
current_graph_objects.append(folkman)
current_graph_objects.append(house)
current_graph_objects.append(subdivided_k5)
current_graph_objects.append(gould)
current_graph_objects.append(grid_2_3)
current_graph_objects.append(grid_3_3_3)
current_graph_objects.append(grid_3_3)
current_graph_objects.append(k_4_6)
current_graph_objects.append(k3_4_edge)
current_graph_objects.append(throwing)
current_graph_objects.append(c5_chord_tail)

#current_graph_objects.append(graphs.FosterGraph())
#order = 90
current_graph_objects.append(graphs.DesarguesGraph())
#current_graph_objects.append(graphs.Tutte12Cage())
#order = 126
#current_graph_objects.append(graphs.BiggsSmithGraph())
#order = 102
current_graph_objects.append(graphs.TutteCoxeterGraph())
current_graph_objects.append(k4)
current_graph_objects.append(graphs.CompleteBipartiteGraph(3,3))
current_graph_objects.append(graphs.PappusGraph())
current_graph_objects.append(graphs.CoxeterGraph())
current_graph_objects.append(graphs.DodecahedralGraph())
current_graph_objects.append(ham1)
current_graph_objects.append(ham2)
current_graph_objects.append(ham3)
current_graph_objects.append(c8_chorded)
current_graph_objects.append(umbrella_4)

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, is_two_connected, alpha_leq_order_over_two]
#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)->((order_leq_twice_max_degree)|(is_locally_bipartite))
(is_hamiltonian)->(((is_regular)->(is_kite_free))&(matching_covered))
(is_hamiltonian)->(((is_regular)->(is_kite_free))&(alpha_leq_order_over_two))
(is_hamiltonian)->((is_independence_irreducible)->(is_anti_tutte))
(is_hamiltonian)->((has_c4)|(has_radius_equal_diameter))
(is_hamiltonian)->(((is_eulerian)|(is_planar))|(has_lovasz_theta_equals_cc))

#Run 2 of Day 9, RERUN
#Return to Sufficient Condition Conjectures

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)
current_graph_objects.append(hoffman)
current_graph_objects.append(robertson)
current_graph_objects.append(folkman)
current_graph_objects.append(house)
current_graph_objects.append(subdivided_k5)
current_graph_objects.append(gould)
current_graph_objects.append(grid_2_3)
current_graph_objects.append(grid_3_3_3)
current_graph_objects.append(grid_3_3)
current_graph_objects.append(k_4_6)
current_graph_objects.append(k3_4_edge)
current_graph_objects.append(throwing)
current_graph_objects.append(c5_chord_tail)

#current_graph_objects.append(graphs.FosterGraph())
#order = 90
current_graph_objects.append(graphs.DesarguesGraph())
#current_graph_objects.append(graphs.Tutte12Cage())
#order = 126
#current_graph_objects.append(graphs.BiggsSmithGraph())
#order = 102
current_graph_objects.append(graphs.TutteCoxeterGraph())
current_graph_objects.append(k4)
current_graph_objects.append(graphs.CompleteBipartiteGraph(3,3))
current_graph_objects.append(graphs.PappusGraph())
current_graph_objects.append(graphs.CoxeterGraph())
current_graph_objects.append(graphs.DodecahedralGraph())
current_graph_objects.append(ham1)
current_graph_objects.append(ham2)
current_graph_objects.append(ham3)
current_graph_objects.append(c8_chorded)
current_graph_objects.append(umbrella_4)

property_of_interest = properties.index(Graph.is_hamiltonian)

theorem_s1 = lambda g: g.is_bipartite() and g.is_strongly_regular()
theorem_s2 = lambda g: g.is_circular_planar() and g.is_cartesian_product()

theorems = [Graph.is_cycle, Graph.is_clique, theorem_s1, is_ore, is_dirac, is_chvatal_erdos, theorem_s2,
is_haggkvist_nicoghossian, is_genghua_fan, is_planar_transitive, is_generalized_dirac, is_lindquester]

precomputed = precomputed_properties_for_conjecture()

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems, time = 5, precomputed = precomputed, verbose=False, debug=True)
for c in conjs:
    print c

> Generation process was stopped by the conjecturing heuristic.
> Found 5 unlabeled trees.
> Found 27602 labeled trees.
> Found 2664 valid expressions.
((is_planar_transitive)|(is_locally_connected))->(is_hamiltonian)
((is_distance_regular)&(is_bipartite))->(is_hamiltonian)
((is_claw_free)&(is_van_den_heuvel))->(is_hamiltonian)
((is_two_connected)&(is_circular_planar))->(is_hamiltonian)
((has_dart)&(is_two_connected))->(is_hamiltonian)
((is_heliotropic_plant)&(is_regular))->(is_hamiltonian)
((~(is_weakly_chordal))&(is_eulerian))->(is_hamiltonian)

#Run 1 of Day 10
#Return to Sufficient Condition Conjectures
#neal gave an original proof of planar & vertex transitive => hamiltonian
#observation: outerplanar and two-connected means no cut vertices, planar embedding, all vertices on the onfinite face, so hamiltonioan
#add as theorem

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)
current_graph_objects.append(hoffman)
current_graph_objects.append(robertson)
current_graph_objects.append(folkman)
current_graph_objects.append(house)
current_graph_objects.append(subdivided_k5)
current_graph_objects.append(gould)
current_graph_objects.append(grid_2_3)
current_graph_objects.append(grid_3_3_3)
current_graph_objects.append(grid_3_3)
current_graph_objects.append(k_4_6)
current_graph_objects.append(k3_4_edge)
current_graph_objects.append(throwing)
current_graph_objects.append(c5_chord_tail)

#current_graph_objects.append(graphs.FosterGraph())
#order = 90
current_graph_objects.append(graphs.DesarguesGraph())
#current_graph_objects.append(graphs.Tutte12Cage())
#order = 126
#current_graph_objects.append(graphs.BiggsSmithGraph())
#order = 102
current_graph_objects.append(graphs.TutteCoxeterGraph())
current_graph_objects.append(k4)
current_graph_objects.append(graphs.CompleteBipartiteGraph(3,3))
current_graph_objects.append(graphs.PappusGraph())
current_graph_objects.append(graphs.CoxeterGraph())
current_graph_objects.append(graphs.DodecahedralGraph())
current_graph_objects.append(ham1)
current_graph_objects.append(ham2)
current_graph_objects.append(ham3)
current_graph_objects.append(c8_chorded)
current_graph_objects.append(umbrella_4)

property_of_interest = properties.index(Graph.is_hamiltonian)

theorem_s1 = lambda g: g.is_bipartite() and g.is_strongly_regular()
theorem_s2 = lambda g: g.is_circular_planar() and g.is_cartesian_product()
theorem_s3 = lambda g: g.is_circular_planar() and g.is_two_connected()

theorems = [Graph.is_cycle, Graph.is_clique, theorem_s1, is_ore, is_dirac, is_chvatal_erdos, theorem_s2,
is_haggkvist_nicoghossian, is_genghua_fan, is_planar_transitive, is_generalized_dirac, is_lindquester, theorem_s3]

precomputed = precomputed_properties_for_conjecture()

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems, time = 5, precomputed = precomputed, verbose=False, debug=True)
for c in conjs:
    print c

> Generation process was stopped by the conjecturing heuristic.
> Found 5 unlabeled trees.
> Found 27602 labeled trees.
> Found 2664 valid expressions.
((is_locally_connected)|(is_generalized_dirac))->(is_hamiltonian)
((is_distance_regular)&(is_bipartite))->(is_hamiltonian)
((is_planar_transitive)|(is_locally_connected))->(is_hamiltonian)
((has_dart)&(is_two_connected))->(is_hamiltonian)
((is_factor_critical)&(is_van_den_heuvel))->(is_hamiltonian)
((is_heliotropic_plant)&(is_regular))->(is_hamiltonian)
((is_heliotropic_plant)&(is_bipartite))->(is_hamiltonian)
((~(is_weakly_chordal))&(is_eulerian))->(is_hamiltonian)

for g in current_graph_objects:
    if is_heliotropic_plant(g):
        print g
        g.show()

Complete graph

Cycle graph

Graph on 5 vertices

Complete graph

Cycle graph

Complete graph

Frucht graph

Heawood graph

House Graph

Complete graph

2D Grid Graph for [2, 3]

Desargues Graph

alpha_critical_C~

Graph on 10 vertices

Graph on 10 vertices

Cycle graph

Graph on 6 vertices

for g in graph_objects:
    if g.order() < 60:
        if g.is_regular() and is_van_den_heuvel(g) and not g.is_hamiltonian():
            print g.name()

Blanusa Second Snark Graph
Coxeter Graph
Double star snark
Ellingham-Horton 54-graph
Flower Snark
Szekeres Snark Graph
Tietze Graph
Tutte Graph
Watkins Snark Graph
alpha_critical_A_
gould
throwing
throwing2
throwing3
binary_octahedron
Barnette-Bosak-Lederberg Graph

for g in graph_objects:
    if g.order() < 60:
        if g.is_bipartite() and is_heliotropic_plant(g) and not g.is_hamiltonian():
            print g.name()

alpha_critical_A_
p4
p6
kratsch_lehel_muller
IhCGGC_@?
Ciliate 4, 1
Ciliate 6, 1
barrus_322111a
barrus_332211c
henning fig 14

throwing2.show()

##Run 2 of Day 10
#Return to Sufficient Condition Conjectures
#add throwing2: CE to ((is_heliotropic_plant)&(is_regular))->(is_hamiltonian)
#add p4: CE to ((is_heliotropic_plant)&(is_bipartite))->(is_hamiltonian)

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)
current_graph_objects.append(hoffman)
current_graph_objects.append(robertson)
current_graph_objects.append(folkman)
current_graph_objects.append(house)
current_graph_objects.append(subdivided_k5)
current_graph_objects.append(gould)
current_graph_objects.append(grid_2_3)
current_graph_objects.append(grid_3_3_3)
current_graph_objects.append(grid_3_3)
current_graph_objects.append(k_4_6)
current_graph_objects.append(k3_4_edge)
current_graph_objects.append(throwing)
current_graph_objects.append(c5_chord_tail)

#current_graph_objects.append(graphs.FosterGraph())
#order = 90
current_graph_objects.append(graphs.DesarguesGraph())
#current_graph_objects.append(graphs.Tutte12Cage())
#order = 126
#current_graph_objects.append(graphs.BiggsSmithGraph())
#order = 102
current_graph_objects.append(graphs.TutteCoxeterGraph())
current_graph_objects.append(k4)
current_graph_objects.append(graphs.CompleteBipartiteGraph(3,3))
current_graph_objects.append(graphs.PappusGraph())
current_graph_objects.append(graphs.CoxeterGraph())
current_graph_objects.append(graphs.DodecahedralGraph())
current_graph_objects.append(ham1)
current_graph_objects.append(ham2)
current_graph_objects.append(ham3)
current_graph_objects.append(c8_chorded)
current_graph_objects.append(umbrella_4)
current_graph_objects.append(throwing2)
current_graph_objects.append(p4)    
    
property_of_interest = properties.index(Graph.is_hamiltonian)

theorem_s1 = lambda g: g.is_bipartite() and g.is_strongly_regular()
theorem_s2 = lambda g: g.is_circular_planar() and g.is_cartesian_product()
theorem_s3 = lambda g: g.is_circular_planar() and g.is_two_connected()

theorems = [Graph.is_cycle, Graph.is_clique, theorem_s1, is_ore, is_dirac, is_chvatal_erdos, theorem_s2,
is_haggkvist_nicoghossian, is_genghua_fan, is_planar_transitive, is_generalized_dirac, is_lindquester, theorem_s3]

precomputed = precomputed_properties_for_conjecture()

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems, time = 5, precomputed = precomputed, verbose=False, debug=True)
for c in conjs:
    print c

> Generation process was stopped by the conjecturing heuristic.
> Found 5 unlabeled trees.
> Found 27602 labeled trees.
> Found 2634 valid expressions.
((~(is_weakly_chordal))&(is_eulerian))->(is_hamiltonian)
((is_distance_regular)&(is_bipartite))->(is_hamiltonian)
((is_planar_transitive)|(is_locally_connected))->(is_hamiltonian)
((has_dart)&(is_two_connected))->(is_hamiltonian)
((is_heliotropic_plant)&(is_two_connected))->(is_hamiltonian)

for g in graph_objects:
    if g.order() < 60:
        if is_two_connected(g) and is_heliotropic_plant(g) and not g.is_hamiltonian():
            print g.name()

kratsch_lehel_muller
willis_page25_fig32
steinberg_ce_g1
barrus_332222d
efl_instance
basic facet-graph three
henning fig 14
henning fig 16 g4

Graph.is_semi_symmetric?

File: /ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/graph.py
Signature : Graph.is_semi_symmetric(self)
Docstring :
Returns true if self is semi-symmetric.

A graph is semi-symmetric if it is regular, edge-transitve but not
vertex-transitive.

See https://en.wikipedia.org/wiki/Semi-symmetric_graph for more
information.

See also:

  * "is_edge_transitive()"

  * "is_arc_transitive()"

  * "is_half_transitive()"

EXAMPLES:

The Petersen graph is not semi-symmetric:

   sage: P = graphs.PetersenGraph()
   sage: P.is_semi_symmetric()
   False

The Gray graph is the smallest possible cubic semi-symmetric graph:

   sage: G = graphs.GrayGraph()
   sage: G.is_semi_symmetric()
   True

Another well known semi-symmetric graph is the Ljubljana graph:

   sage: L = graphs.LjubljanaGraph()
   sage: L.is_semi_symmetric()
   True

##Run 3 of Day 10

##kratsch_lehel_muller graph is an example of a bipartite, 1-tough, not van_den_heuvel, not hamiltonian graph
#add kratsch_lehel_muller

#Return to Sufficient Condition Conjectures

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)
current_graph_objects.append(hoffman)
current_graph_objects.append(robertson)
current_graph_objects.append(folkman)
current_graph_objects.append(house)
current_graph_objects.append(subdivided_k5)
current_graph_objects.append(gould)
current_graph_objects.append(grid_2_3)
current_graph_objects.append(grid_3_3_3)
current_graph_objects.append(grid_3_3)
current_graph_objects.append(k_4_6)
current_graph_objects.append(k3_4_edge)
current_graph_objects.append(throwing)
current_graph_objects.append(c5_chord_tail)

#current_graph_objects.append(graphs.FosterGraph())
#order = 90
current_graph_objects.append(graphs.DesarguesGraph())
#current_graph_objects.append(graphs.Tutte12Cage())
#order = 126
#current_graph_objects.append(graphs.BiggsSmithGraph())
#order = 102
current_graph_objects.append(graphs.TutteCoxeterGraph())
current_graph_objects.append(k4)
current_graph_objects.append(graphs.CompleteBipartiteGraph(3,3))
current_graph_objects.append(graphs.PappusGraph())
current_graph_objects.append(graphs.CoxeterGraph())
current_graph_objects.append(graphs.DodecahedralGraph())
current_graph_objects.append(ham1)
current_graph_objects.append(ham2)
current_graph_objects.append(ham3)
current_graph_objects.append(c8_chorded)
current_graph_objects.append(umbrella_4)
current_graph_objects.append(throwing2)
current_graph_objects.append(p4)  
current_graph_objects.append(kratsch_lehel_muller)
    
property_of_interest = properties.index(Graph.is_hamiltonian)

theorem_s1 = lambda g: g.is_bipartite() and g.is_strongly_regular()
theorem_s2 = lambda g: g.is_circular_planar() and g.is_cartesian_product()
theorem_s3 = lambda g: g.is_circular_planar() and g.is_two_connected()

theorems = [Graph.is_cycle, Graph.is_clique, theorem_s1, is_ore, is_dirac, is_chvatal_erdos, theorem_s2,
is_haggkvist_nicoghossian, is_genghua_fan, is_planar_transitive, is_generalized_dirac, is_lindquester, theorem_s3]

precomputed = precomputed_properties_for_conjecture()

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems, time = 5, precomputed = precomputed, verbose=False, debug=True)
for c in conjs:
    print c

> Generation process was stopped by the conjecturing heuristic.
> Found 9 unlabeled trees.
> Found 418111 labeled trees.
> Found 33436 valid expressions.
((is_locally_connected)|(is_generalized_dirac))->(is_hamiltonian)
(((is_circular_planar)->(order_leq_twice_max_degree))->(is_locally_connected))->(is_hamiltonian)
((is_distance_regular)&(is_bipartite))->(is_hamiltonian)
((is_planar_transitive)|(is_locally_connected))->(is_hamiltonian)
((has_dart)&(is_two_connected))->(is_hamiltonian)
(((is_cartesian_product)&(is_circular_planar))|(is_locally_connected))->(is_hamiltonian)
((is_heliotropic_plant)&(is_three_connected))->(is_hamiltonian)
((~(is_weakly_chordal))&(is_eulerian))->(is_hamiltonian)

g.order()>50

False

for g in graph_objects:
    if g.order() < 60:
        if has_dart(g) and is_two_connected(g) and not g.is_hamiltonian():
            print g.name()

Goldner-Harary graph
starfish
ce17
ce23
ce77
ce80
ce109
ce129
triangle_star
willis_page25_fig32
Lemke
chartrand fig 1.8 - F2
barrus_442222b
efl_instance

starfish.show()

#adding starfish: ((has_dart)&(is_two_connected))->(is_hamiltonian)

##Run 4 of Day 10
#Return to Sufficient Condition Conjectures

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)
current_graph_objects.append(hoffman)
current_graph_objects.append(robertson)
current_graph_objects.append(folkman)
current_graph_objects.append(house)
current_graph_objects.append(subdivided_k5)
current_graph_objects.append(gould)
current_graph_objects.append(grid_2_3)
current_graph_objects.append(grid_3_3_3)
current_graph_objects.append(grid_3_3)
current_graph_objects.append(k_4_6)
current_graph_objects.append(k3_4_edge)
current_graph_objects.append(throwing)
current_graph_objects.append(c5_chord_tail)

#current_graph_objects.append(graphs.FosterGraph())
#order = 90
current_graph_objects.append(graphs.DesarguesGraph())
#current_graph_objects.append(graphs.Tutte12Cage())
#order = 126
#current_graph_objects.append(graphs.BiggsSmithGraph())
#order = 102
current_graph_objects.append(graphs.TutteCoxeterGraph())
current_graph_objects.append(k4)
current_graph_objects.append(graphs.CompleteBipartiteGraph(3,3))
current_graph_objects.append(graphs.PappusGraph())
current_graph_objects.append(graphs.CoxeterGraph())
current_graph_objects.append(graphs.DodecahedralGraph())
current_graph_objects.append(ham1)
current_graph_objects.append(ham2)
current_graph_objects.append(ham3)
current_graph_objects.append(c8_chorded)
current_graph_objects.append(umbrella_4)
current_graph_objects.append(throwing2)
current_graph_objects.append(p4)  
current_graph_objects.append(kratsch_lehel_muller)
current_graph_objects.append(starfish)    
    
property_of_interest = properties.index(Graph.is_hamiltonian)

theorem_s1 = lambda g: g.is_bipartite() and g.is_strongly_regular()
theorem_s2 = lambda g: g.is_circular_planar() and g.is_cartesian_product()
theorem_s3 = lambda g: g.is_circular_planar() and g.is_two_connected()

theorems = [Graph.is_cycle, Graph.is_clique, theorem_s1, is_ore, is_dirac, is_chvatal_erdos, theorem_s2,
is_haggkvist_nicoghossian, is_genghua_fan, is_planar_transitive, is_generalized_dirac, is_lindquester, theorem_s3]

precomputed = precomputed_properties_for_conjecture()

conjs = propertyBasedConjecture(current_graph_objects, properties, property_of_interest, theory = theorems, time = 5, precomputed = precomputed, verbose=False, debug=True)
for c in conjs:
    print c

> Generation process was stopped by the conjecturing heuristic.
> Found 9 unlabeled trees.
> Found 418271 labeled trees.
> Found 29675 valid expressions.
((is_heliotropic_plant)&(is_three_connected))->(is_hamiltonian)
((is_independence_irreducible)&(has_dart))->(is_hamiltonian)
((is_perfect)&(is_distance_regular))->(is_hamiltonian)
((has_k4)&(has_residue_equals_two))->(is_hamiltonian)
((is_planar_transitive)|(is_semi_symmetric))->(is_hamiltonian)
((is_factor_critical)&(is_van_den_heuvel))->(is_hamiltonian)
((~(is_weakly_chordal))&(is_eulerian))->(is_hamiltonian)
(((is_cartesian_product)&(is_circular_planar))|(is_semi_symmetric))->(is_hamiltonian)

#make a list of the graph_objects with less than 50 vertices
graphs50 = []
for g in graph_objects:
    if g.order() < 50:
        graphs50.append(g)
len(graphs50)

459

#2nd approach using list comprehension
graphs50 = [g for g in graph_objects if g.order() < 50]
len(graphs50)

459

#(is_hamiltonian)->((order_leq_twice_max_degree)|(is_locally_bipartite))
#(is_hamiltonian)->(((is_regular)->(is_kite_free))&(matching_covered))
#(is_hamiltonian)->(((is_regular)->(is_kite_free))&(alpha_leq_order_over_two))
#(is_hamiltonian)->((is_independence_irreducible)->(is_anti_tutte))
#(is_hamiltonian)->((has_c4)|(has_radius_equal_diameter))
#(is_hamiltonian)->(((is_eulerian)|(is_planar))|(has_lovasz_theta_equals_cc))

k1=Graph(1)
k1.is_hamiltonian()

False

harborth = graphs.HarborthGraph()
harborth.show()

#INVSETIGATE: (is_hamiltonian)->((is_independence_irreducible)->(is_anti_tutte))
#anti-tutte <=>  independence_number(g) <= g.diameter() + g.girth()
names = []
for g in graph_objects:
    if g.order() < 60:
        if g.is_hamiltonian() and is_independence_irreducible(g) and not is_anti_tutte(g):
            #print g.order()
            names.append(g.name())
            #g.show()
names

['Harborth Graph', 'Hoffman-Singleton graph', 'Holt graph', 'Klein 3-regular Graph', 'Perkel Graph', 'Sims-Gewirtz Graph', 'Sylvester Graph', 'Wells graph', 'c7xc7', 'ce16', 'ce22', 'ce31', 'ce33', 'ce54', 'ce57', 'ce60', 'ce62', 'ce72', 'ce73', 'ce85', 'ce86', 'ce88', 'ce95', 'ce105', 'ce132', 'ce134', 'willis_page29', 'steinberg_ce_g2', 'steffen_3']

['Harborth Graph', 'Hoffman-Singleton graph', 'Holt graph', 'Klein 3-regular Graph', 'Perkel Graph', 'Sims-Gewirtz Graph', 'Sylvester Graph', 'Wells graph', 'c7xc7', 'ce16', 'ce22', 'ce31', 'ce33', 'ce54', 'ce57', 'ce60', 'ce62', 'ce72', 'ce73', 'ce85', 'ce86', 'ce88', 'ce95', 'ce105', 'ce132', 'ce134', 'willis_page29', 'steinberg_ce_g2', 'steffen_3']

#CONJECTURE: #(is_hamiltonian)->((is_independence_irreducible)->(is_anti_tutte)) is false
#many CE's in gt.sage including: steffen_3, graphs

binomial(100,3)

161700

g.vertex_connectivity??

   File: /ext/sage/sage-8.1/local/lib/python2.7/site-packages/sage/graphs/generic_graph.py
   Source:
       def vertex_connectivity(self, value_only=True, sets=False, solver=None, verbose=0):
        r"""
        Returns the vertex connectivity of the graph. For more information,
        see the
        `Wikipedia article on connectivity
        <http://en.wikipedia.org/wiki/Connectivity_(graph_theory)>`_.

        .. NOTE::

            * When the graph is a directed graph, this method actually computes
              the *strong* connectivity, (i.e. a directed graph is strongly
              `k`-connected if there are `k` disjoint paths between any two
              vertices `u, v`). If you do not want to consider strong
              connectivity, the best is probably to convert your ``DiGraph``
              object to a ``Graph`` object, and compute the connectivity of this
              other graph.

            * By convention, a complete graph on `n` vertices is `n-1`
              connected. In this case, no certificate can be given as there is
              no pair of vertices split by a cut of size `k-1`. For this reason,
              the certificates returned in this situation are empty.

        INPUT:

        - ``value_only`` -- boolean (default: ``True``)

          - When set to ``True`` (default), only the value is returned.

          - When set to ``False`` , both the value and a minimum vertex cut are
            returned.

        - ``sets`` -- boolean (default: ``False``)

          - When set to ``True``, also returns the two sets of
            vertices that are disconnected by the cut.
            Implies ``value_only=False``

        - ``solver`` -- (default: ``None``) Specify a Linear Program (LP)
          solver to be used. If set to ``None``, the default one is used. For
          more information on LP solvers and which default solver is used, see
          the method
          :meth:`solve <sage.numerical.mip.MixedIntegerLinearProgram.solve>`
          of the class
          :class:`MixedIntegerLinearProgram <sage.numerical.mip.MixedIntegerLinearProgram>`.

        - ``verbose`` -- integer (default: ``0``). Sets the level of
          verbosity. Set to 0 by default, which means quiet.

        EXAMPLES:

        A basic application on a ``PappusGraph``::

           sage: g=graphs.PappusGraph()
           sage: g.vertex_connectivity()
           3

        In a grid, the vertex connectivity is equal to the
        minimum degree, in which case one of the two sets is
        of cardinality `1`::

           sage: g = graphs.GridGraph([ 3,3 ])
           sage: [value, cut, [ setA, setB ]] = g.vertex_connectivity(sets=True)
           sage: len(setA) == 1 or len(setB) == 1
           True

        A vertex cut in a tree is any internal vertex::

           sage: g = graphs.RandomGNP(15,.5)
           sage: tree = Graph()
           sage: tree.add_edges(g.min_spanning_tree())
           sage: [val, [cut_vertex]] = tree.vertex_connectivity(value_only=False)
           sage: tree.degree(cut_vertex) > 1
           True

        When ``value_only = True``, this function is optimized for small
        connectivity values and does not need to build a linear program.

        It is the case for connected graphs which are not connected::

           sage: g = 2 * graphs.PetersenGraph()
           sage: g.vertex_connectivity()
           0

        Or if they are just 1-connected::

           sage: g = graphs.PathGraph(10)
           sage: g.vertex_connectivity()
           1

        For directed graphs, the strong connectivity is tested
        through the dedicated function::

           sage: g = digraphs.ButterflyGraph(3)
           sage: g.vertex_connectivity()
           0

        A complete graph on `10` vertices is `9`-connected::

           sage: g = graphs.CompleteGraph(10)
           sage: g.vertex_connectivity()
           9

        A complete digraph on `10` vertices is `9`-connected::

           sage: g = DiGraph(graphs.CompleteGraph(10))
           sage: g.vertex_connectivity()
           9
        """
        g=self

        if sets:
            value_only=False

        # When the graph is complete, the MILP below is infeasible.
        if ((not g.is_directed() and g.is_clique())
            or
            (g.is_directed() and g.size() >= (g.order()-1)*g.order() and
             ((not g.allows_loops() and not g.allows_multiple_edges())
              or
              all(g.has_edge(u,v) for u in g for v in g if v != u)))):
            if value_only:
                return g.order()-1
            elif not sets:
                return g.order()-1, []
            else:
                return g.order()-1, [], [[],[]]

        if value_only:
            if self.is_directed():
                if not self.is_strongly_connected():
                    return 0

            else:
                if not self.is_connected():
                    return 0

                if len(self.blocks_and_cut_vertices()[0]) > 1:
                    return 1

        if g.is_directed():
            reorder_edge = lambda x,y : (x,y)
        else:
            reorder_edge = lambda x,y : (x,y) if x<= y else (y,x)

        from sage.numerical.mip import MixedIntegerLinearProgram

        p = MixedIntegerLinearProgram(maximization=False, solver=solver)

        # Sets 0 and 2 are "real" sets while set 1 represents the cut
        in_set = p.new_variable(binary=True)

        # A vertex has to be in some set
        for v in g:
            p.add_constraint(in_set[0,v]+in_set[1,v]+in_set[2,v],max=1,min=1)

        # There is no empty set
        p.add_constraint(p.sum([in_set[0,v] for v in g]),min=1)
        p.add_constraint(p.sum([in_set[2,v] for v in g]),min=1)

        if g.is_directed():
            # There is no edge from set 0 to set 1 which
            # is not in the cut
            for (u,v) in g.edge_iterator(labels=None):
                p.add_constraint(in_set[0,u] + in_set[2,v], max = 1)
        else:

            # Two adjacent vertices are in different sets if and only if
            # the edge between them is in the cut

            for (u,v) in g.edge_iterator(labels=None):
                p.add_constraint(in_set[0,u]+in_set[2,v],max=1)
                p.add_constraint(in_set[2,u]+in_set[0,v],max=1)

        p.set_binary(in_set)

        p.set_objective(p.sum([in_set[1,v] for v in g]))

        if value_only:
            return Integer(round(p.solve(objective_only=True, log=verbose)))
        else:
            val = [Integer(round(p.solve(log=verbose)))]

            in_set = p.get_values(in_set)

            cut = []
            a = []
            b = []

            for v in g:
                if in_set[0,v] == 1:
                    a.append(v)
                elif in_set[1,v]==1:
                    cut.append(v)
                else:
                    b.append(v)

            val.append(cut)

            if sets:
                val.append([a,b])

            return val

kratsch_lehel_muller.show()

version()

'SageMath version 8.1, Release Date: 2017-12-07'

#Run 3 of Day 9, 
#necessary condition conjectures
##CONJECTURE: #(is_hamiltonian)->((is_independence_irreducible)->(is_anti_tutte)) is false
#many CE's in gt.sage including: steffen_3, graphs
#['Harborth Graph', 'Hoffman-Singleton graph', 'Holt graph', 'Klein 3-regular Graph', 'Perkel Graph', 'Sims-Gewirtz Graph', 'Sylvester Graph', 'Wells graph', 'c7xc7', 'ce16', 'ce22', 'ce31', 'ce33', 'ce54', 'ce57', 'ce60', 'ce62', 'ce72', 'ce73', 'ce85', 'ce86', 'ce88', 'ce95', 'ce105', 'ce132', 'ce134', 'willis_page29', 'steinberg_ce_g2', 'steffen_3']

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)
current_graph_objects.append(hoffman)
current_graph_objects.append(robertson)
current_graph_objects.append(folkman)
current_graph_objects.append(house)
current_graph_objects.append(subdivided_k5)
current_graph_objects.append(gould)
current_graph_objects.append(grid_2_3)
current_graph_objects.append(grid_3_3_3)
current_graph_objects.append(grid_3_3)
current_graph_objects.append(k_4_6)
current_graph_objects.append(k3_4_edge)
current_graph_objects.append(throwing)
current_graph_objects.append(c5_chord_tail)

#current_graph_objects.append(graphs.FosterGraph())
#order = 90
current_graph_objects.append(graphs.DesarguesGraph())
#current_graph_objects.append(graphs.Tutte12Cage())
#order = 126
#current_graph_objects.append(graphs.BiggsSmithGraph())
#order = 102
current_graph_objects.append(graphs.TutteCoxeterGraph())
current_graph_objects.append(k4)
current_graph_objects.append(graphs.CompleteBipartiteGraph(3,3))
current_graph_objects.append(graphs.PappusGraph())
current_graph_objects.append(graphs.CoxeterGraph())
current_graph_objects.append(graphs.DodecahedralGraph())
current_graph_objects.append(ham1)
current_graph_objects.append(ham2)
current_graph_objects.append(ham3)
current_graph_objects.append(c8_chorded)
current_graph_objects.append(umbrella_4)
current_graph_objects.append(throwing2)
current_graph_objects.append(p4)  
current_graph_objects.append(kratsch_lehel_muller)
current_graph_objects.append(starfish) 
current_graph_objects.append(graphs.HarborthGraph())
current_graph_objects.append(graphs.HoffmanSingletonGraph())
current_graph_objects.append(graphs.HoltGraph())
current_graph_objects.append(graphs.Klein3RegularGraph())
current_graph_objects.append(graphs.PerkelGraph())
current_graph_objects.append(graphs.SimsGewirtzGraph())
current_graph_objects.append(graphs.SylvesterGraph())
current_graph_objects.append(graphs.WellsGraph())                            
current_graph_objects.append(c7xc7)
current_graph_objects.append(ce16)                                    
current_graph_objects.append(ce22)
current_graph_objects.append(ce22)
current_graph_objects.append(ce31)                                                    
current_graph_objects.append(ce33)                                                    
current_graph_objects.append(ce54)
current_graph_objects.append(ce57)
current_graph_objects.append(ce60)
current_graph_objects.append(ce62)
current_graph_objects.append(ce72)
current_graph_objects.append(ce73)
current_graph_objects.append(ce85)
current_graph_objects.append(ce86)
current_graph_objects.append(ce88)
current_graph_objects.append(ce95)
current_graph_objects.append(ce105)
current_graph_objects.append(ce132)
current_graph_objects.append(ce134)
current_graph_objects.append(willis_page29)
current_graph_objects.append(steinberg_ce_g2)
current_graph_objects.append(steffen_3)

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, is_two_connected, alpha_leq_order_over_two]
#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

load("gt.sage")

loaded utilities
loaded invariants
loaded properties
loaded theorems
loaded graphs

Remember to load DIMACS and Sloane graphs if you want them

for p in properties:
    print p.__name__

is_regular
is_planar
is_forest
is_eulerian
is_connected
is_clique
is_circular_planar
is_chordal
is_bipartite
is_cartesian_product
is_distance_regular
is_even_hole_free
is_gallai_tree
is_line_graph
is_overfull
is_perfect
is_split
is_strongly_regular
is_triangle_free
is_weakly_chordal
is_dirac
is_ore
is_haggkvist_nicoghossian
is_generalized_dirac
is_van_den_heuvel
is_two_connected
is_three_connected
is_lindquester
is_claw_free
has_perfect_matching
has_radius_equal_diameter
is_not_forest
is_genghua_fan
is_cubic
diameter_equals_twice_radius
diameter_equals_radius
is_locally_connected
matching_covered
is_locally_dirac
is_locally_bipartite
is_locally_two_connected
is_interval
has_paw
is_paw_free
has_p4
is_p4_free
has_dart
is_dart_free
has_kite
is_kite_free
has_H
is_H_free
has_residue_equals_two
order_leq_twice_max_degree
alpha_leq_order_over_two
is_factor_critical
is_independence_irreducible
has_twin
is_twin_free
diameter_equals_two
girth_greater_than_2log
is_cycle
pairs_have_unique_common_neighbor
has_star_center
is_complement_of_chordal
has_c4
is_c4_free
is_subcubic
is_quasi_regular
is_bad
has_k4
is_k4_free
is_distance_transitive
is_hamiltonian
is_vertex_transitive
is_edge_transitive
has_residue_equals_alpha
is_odd_hole_free
is_semi_symmetric
is_line_graph
is_planar_transitive
is_class1
is_class2
is_anti_tutte
is_anti_tutte2
has_lovasz_theta_equals_cc
has_lovasz_theta_equals_alpha
is_chvatal_erdos
is_heliotropic_plant
is_geotropic_plant
is_traceable
is_chordal_or_not_perfect
has_alpha_residue_equal_two
is_complement_hamiltonian

bus = graphs.CycleGraph(4)
bus.add_vertex(4)
bus.add_edges([(0,4),(2,4),(0,2)])

is_generalized_dirac(bus)

Error in lines 1-1
Traceback (most recent call last):
  File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1044, in execute
    exec compile(block+'\n', '', 'single', flags=compile_flags) in namespace, locals
  File "", line 1, in <module>
NameError: name 'is_generalized_dirac' is not defined

paw.show()

for g in graph_objects:
    if is_factor_critical(g) and not g.is_hamiltonian():
        print g.name()
        g.show()

Butterfly graph

c5c5

c5k3

binary_octahedron

pepper_residue_graph

flower_with_3_petals

flower_with_4_petals

steinberg_ce_g1

efl_instance

basic facet-graph

basic facet-graph three

critical facet graph 2

henning fig 16 g4

Cycle graph

basic_facet_1

basic facet-graph: Graph on 7 vertices

is_van_den_heuvel(basic_facet_1)

False

for g in graph_objects:
    if g.order() == 20 and g.is_regular():
        print g.name()
        g.show()

Desargues Graph

Flower Snark

Folkman Graph

Dodecahedron

gould

ce86

jorgenson_1

Barnette-Bosak-Lederberg Graph

for g

Product

Resources

Company