finding_counterexamples.sagews

#example conjectures for the purposes of finding counterexamples

load("conjecturing.py")

p3 = graphs.PathGraph(3)
k3 = graphs.CompleteGraph(3)
pete = graphs.PetersenGraph()

def independence_number(g):
    return len(g.independent_set())

objects = [p3, k3, pete]

invariants = [independence_number, Graph.order, Graph.size]

#we'll give a name to the out list of conjectures so that we can grab them

conjs = conjecture(objects, invariants, invariants.index(independence_number))

for c in conjs:
    print c

independence_number(x) <= floor(10^sin(size(x))) independence_number(x) <= size(x) independence_number(x) <= ceil(sqrt(order(x)))

conjs[0]

independence_number(x) <= floor(10^sin(size(x)))

#we'd like to test a conjecture againt a graph
conjs[0](p3)

True

[conjs[i](p3) for i in range(len(conjs))]

[True, True, True]

all([conjs[i](p3) for i in range(len(conjs))])

True

#now lets test conjecture[0] against all the graphs stored in gt.sage
load("gt.sage")

loaded graph dc1024 loaded graph dc2048 loaded graph properties data file loaded graph invariants data file

# the graphs are all in a list called graph_objects
graph_objects

[paw: Graph on 4 vertices, kite: Graph on 4 vertices, p4: Graph on 4 vertices, dart: Graph on 5 vertices, k3: Graph on 3 vertices, k4: Graph on 4 vertices, k5: Graph on 5 vertices, c6ee: Graph on 6 vertices, c5chord: Graph on 5 vertices, Dodecahedron: Graph on 20 vertices, c8chorded: Graph on 8 vertices, c8chords: Graph on 8 vertices, Clebsch graph: Graph on 16 vertices, prismy: Graph on 8 vertices, c24: Graph on 24 vertices, c26: Graph on 26 vertices, c60: Graph on 60 vertices, c6xc6: Graph on 36 vertices, holton_mckay: Graph on 24 vertices, sixfour: Graph on 10 vertices, c4: Graph on 4 vertices, Petersen graph: Graph on 10 vertices, p2: Graph on 2 vertices, Tutte Graph: Graph on 46 vertices, non_ham_over: Graph on 9 vertices, throwing: Graph on 11 vertices, throwing2: Graph on 12 vertices, throwing3: Graph on 12 vertices, kratsch_lehel_muller: Graph on 12 vertices, Blanusa First Snark Graph: Graph on 18 vertices, Blanusa Second Snark Graph: Graph on 18 vertices, Flower Snark: Graph on 20 vertices, s3: Graph on 4 vertices, ryan3: Graph on 15 vertices, k10: Graph on 10 vertices, Mycielski Graph 5: Graph on 23 vertices, c3mycieski: Graph on 7 vertices, s13e: Graph on 14 vertices, circulant_50_1_3: Graph on 50 vertices, s22e: Graph on 23 vertices, difficult11: Graph on 11 vertices, Bull graph: Graph on 5 vertices, Chvatal graph: Graph on 12 vertices, Claw graph: Graph on 4 vertices, Desargues Graph: Graph on 20 vertices, Diamond Graph: Graph on 4 vertices, Flower Snark: Graph on 20 vertices, Frucht graph: Graph on 12 vertices, Hoffman-Singleton graph: Graph on 50 vertices, House Graph: Graph on 5 vertices, Octahedron: Graph on 6 vertices, Thomsen graph: Graph on 6 vertices, Petersen graph: Graph on 10 vertices, Pappus Graph: Graph on 18 vertices, Grotzsch graph: Graph on 11 vertices, Gray graph: Graph on 54 vertices, Heawood graph: Graph on 14 vertices, Herschel graph: Graph on 11 vertices, Coxeter Graph: Graph on 28 vertices, Brinkmann graph: Graph on 21 vertices, Tutte-Coxeter graph: Graph on 30 vertices, Tutte Graph: Graph on 46 vertices, Robertson Graph: Graph on 19 vertices, Folkman Graph: Graph on 20 vertices, Balaban 10-cage: Graph on 70 vertices, Pappus Graph: Graph on 18 vertices, Tietze Graph: Graph on 12 vertices, Sylvester Graph: Graph on 36 vertices, Szekeres Snark Graph: Graph on 50 vertices, Moebius-Kantor Graph: Graph on 16 vertices, ryan: Graph on 24 vertices, inp: Graph on 11 vertices, c4c4: Graph on 7 vertices, regular_non_trans: Graph on 8 vertices, bridge: Graph on 5 vertices, p10k4: Graph on 14 vertices, c100: Graph on 100 vertices, starfish: Graph on 15 vertices, c5k3: Graph on 7 vertices, k5pendant: Graph on 6 vertices, Shrikhande graph: Graph on 16 vertices, sylvester: Graph on 16 vertices, fork: Graph on 5 vertices, edge_critical_5: Graph on 5 vertices, edge_critical_11_1: Graph on 11 vertices, edge_critical_11_2: Graph on 11 vertices, pete_minus: Graph on 9 vertices, c5: Graph on 5 vertices, bow_tie: Graph on 5 vertices, pepper_residue_graph: Graph on 13 vertices, barrus_graph: Graph on 9 vertices, p5: Graph on 5 vertices, c6: Graph on 6 vertices, c9: Graph on 9 vertices, ce3: Graph on 8 vertices, ce4: Graph on 8 vertices, ce5: Graph on 25 vertices, k4e2split: Graph on 6 vertices, flower_with_3_petals: Graph on 7 vertices, flower_with_4_petals: Graph on 9 vertices, paw_x_paw: Graph on 16 vertices, Wagner Graph: Graph on 8 vertices, houseX: Graph on 5 vertices, ce7: Graph on 7 vertices, triangle_star: Graph on 9 vertices, ce8: Graph on 10 vertices, ce9: Graph on 10 vertices, ce10: Graph on 12 vertices, p3: Graph on 3 vertices, binary_octahedron: Graph on 13 vertices, ce11: Graph on 6 vertices, prism: Graph on 6 vertices, ce12: Graph on 6 vertices, ce13: Graph on 6 vertices, IhCGGC_@?: Graph on 10 vertices, alpha_critical_A_: Graph on 2 vertices, alpha_critical_Bw: Graph on 3 vertices, alpha_critical_C~: Graph on 4 vertices, alpha_critical_Dhc: Graph on 5 vertices, alpha_critical_D~{: Graph on 5 vertices, alpha_critical_E|OW: Graph on 6 vertices, alpha_critical_E~~w: Graph on 6 vertices, alpha_critical_FhCKG: Graph on 7 vertices, alpha_critical_F~[KG: Graph on 7 vertices, alpha_critical_FzEKW: Graph on 7 vertices, alpha_critical_Fn[kG: Graph on 7 vertices, alpha_critical_F~~~w: Graph on 7 vertices, alpha_critical_GbL|TS: Graph on 8 vertices, alpha_critical_G~?mvc: Graph on 8 vertices, alpha_critical_GbMmvG: Graph on 8 vertices, alpha_critical_Gb?kTG: Graph on 8 vertices, alpha_critical_GzD{Vg: Graph on 8 vertices, alpha_critical_Gb?kR_: Graph on 8 vertices, alpha_critical_GbqlZ_: Graph on 8 vertices, alpha_critical_GbilZ_: Graph on 8 vertices, alpha_critical_G~~~~{: Graph on 8 vertices, alpha_critical_GbDKPG: Graph on 8 vertices, alpha_critical_HzCGKFo: Graph on 9 vertices, alpha_critical_H~|wKF{: Graph on 9 vertices, alpha_critical_HnLk]My: Graph on 9 vertices, alpha_critical_HhcWKF_: Graph on 9 vertices, alpha_critical_HhKWKF_: Graph on 9 vertices, alpha_critical_HhCW[F_: Graph on 9 vertices, alpha_critical_HxCw}V`: Graph on 9 vertices, alpha_critical_HhcGKf_: Graph on 9 vertices, alpha_critical_HhKGKf_: Graph on 9 vertices, alpha_critical_Hh[gMEO: Graph on 9 vertices, alpha_critical_HhdGKE[: Graph on 9 vertices, alpha_critical_HhcWKE[: Graph on 9 vertices, alpha_critical_HhdGKFK: Graph on 9 vertices, alpha_critical_HhCGGE@: Graph on 9 vertices, alpha_critical_Hn[gGE@: Graph on 9 vertices, alpha_critical_Hn^zxU@: Graph on 9 vertices, alpha_critical_HlDKhEH: Graph on 9 vertices, alpha_critical_H~~~~~~: Graph on 9 vertices, alpha_critical_HnKmH]N: Graph on 9 vertices, alpha_critical_HnvzhEH: Graph on 9 vertices, alpha_critical_HhfJGE@: Graph on 9 vertices, alpha_critical_HhdJGM@: Graph on 9 vertices, alpha_critical_Hj~KHeF: Graph on 9 vertices, alpha_critical_HhdGHeB: Graph on 9 vertices, alpha_critical_HhXg[EO: Graph on 9 vertices, alpha_critical_HhGG]ES: Graph on 9 vertices, alpha_critical_H~Gg]f{: Graph on 9 vertices, alpha_critical_H~?g]vs: Graph on 9 vertices, alpha_critical_H~@w[Vs: Graph on 9 vertices, alpha_critical_Hn_k[^o: Graph on 9 vertices]

for g in graph_objects:
    print g.name(), g.order()

paw 4 kite 4 p4 4 dart 5 k3 3 k4 4 k5 5 c6ee 6 c5chord 5 Dodecahedron 20 c8chorded 8 c8chords 8 Clebsch graph 16 prismy 8 c24 24 c26 26 c60 60 c6xc6 36 holton_mckay 24 sixfour 10 c4 4 Petersen graph 10 p2 2 Tutte Graph 46 non_ham_over 9 throwing 11 throwing2 12 throwing3 12 kratsch_lehel_muller 12 Blanusa First Snark Graph 18 Blanusa Second Snark Graph 18 Flower Snark 20 s3 4 ryan3 15 k10 10 Mycielski Graph 5 23 c3mycieski 7 s13e 14 circulant_50_1_3 50 s22e 23 difficult11 11 Bull graph 5 Chvatal graph 12 Claw graph 4 Desargues Graph 20 Diamond Graph 4 Flower Snark 20 Frucht graph 12 Hoffman-Singleton graph 50 House Graph 5 Octahedron 6 Thomsen graph 6 Petersen graph 10 Pappus Graph 18 Grotzsch graph 11 Gray graph 54 Heawood graph 14 Herschel graph 11 Coxeter Graph 28 Brinkmann graph 21 Tutte-Coxeter graph 30 Tutte Graph 46 Robertson Graph 19 Folkman Graph 20 Balaban 10-cage 70 Pappus Graph 18 Tietze Graph 12 Sylvester Graph 36 Szekeres Snark Graph 50 Moebius-Kantor Graph 16 ryan 24 inp 11 c4c4 7 regular_non_trans 8 bridge 5 p10k4 14 c100 100 starfish 15 c5k3 7 k5pendant 6 Shrikhande graph 16 sylvester 16 fork 5 edge_critical_5 5 edge_critical_11_1 11 edge_critical_11_2 11 pete_minus 9 c5 5 bow_tie 5 pepper_residue_graph 13 barrus_graph 9 p5 5 c6 6 c9 9 ce3 8 ce4 8 ce5 25 k4e2split 6 flower_with_3_petals 7 flower_with_4_petals 9 paw_x_paw 16 Wagner Graph 8 houseX 5 ce7 7 triangle_star 9 ce8 10 ce9 10 ce10 12 p3 3 binary_octahedron 13 ce11 6 prism 6 ce12 6 ce13 6 IhCGGC_@? 10 alpha_critical_A_ 2 alpha_critical_Bw 3 alpha_critical_C~ 4 alpha_critical_Dhc 5 alpha_critical_D~{ 5 alpha_critical_E|OW 6 alpha_critical_E~~w 6 alpha_critical_FhCKG 7 alpha_critical_F~[KG 7 alpha_critical_FzEKW 7 alpha_critical_Fn[kG 7 alpha_critical_F~~~w 7 alpha_critical_GbL|TS 8 alpha_critical_G~?mvc 8 alpha_critical_GbMmvG 8 alpha_critical_Gb?kTG 8 alpha_critical_GzD{Vg 8 alpha_critical_Gb?kR_ 8 alpha_critical_GbqlZ_ 8 alpha_critical_GbilZ_ 8 alpha_critical_G~~~~{ 8 alpha_critical_GbDKPG 8 alpha_critical_HzCGKFo 9 alpha_critical_H~|wKF{ 9 alpha_critical_HnLk]My 9 alpha_critical_HhcWKF_ 9 alpha_critical_HhKWKF_ 9 alpha_critical_HhCW[F_ 9 alpha_critical_HxCw}V` 9 alpha_critical_HhcGKf_ 9 alpha_critical_HhKGKf_ 9 alpha_critical_Hh[gMEO 9 alpha_critical_HhdGKE[ 9 alpha_critical_HhcWKE[ 9 alpha_critical_HhdGKFK 9 alpha_critical_HhCGGE@ 9 alpha_critical_Hn[gGE@ 9 alpha_critical_Hn^zxU@ 9 alpha_critical_HlDKhEH 9 alpha_critical_H~~~~~~ 9 alpha_critical_HnKmH]N 9 alpha_critical_HnvzhEH 9 alpha_critical_HhfJGE@ 9 alpha_critical_HhdJGM@ 9 alpha_critical_Hj~KHeF 9 alpha_critical_HhdGHeB 9 alpha_critical_HhXg[EO 9 alpha_critical_HhGG]ES 9 alpha_critical_H~Gg]f{ 9 alpha_critical_H~?g]vs 9 alpha_critical_H~@w[Vs 9 alpha_critical_Hn_k[^o 9

#now lets check the truth of conjecture[0] for these graphs
for g in graph_objects:
    print g.name(), conjs[0](g)

paw False kite False p4 False dart False k3 True k4 False k5 False c6ee True c5chord False Dodecahedron False c8chorded False c8chords False Clebsch graph True prismy False c24 False c26 False c60 False c6xc6 False holton_mckay False sixfour True c4 False Petersen graph True p2 True Tutte Graph False non_ham_over False throwing False throwing2 False throwing3 False kratsch_lehel_muller False Blanusa First Snark Graph True Blanusa Second Snark Graph True Flower Snark False s3 False ryan3 True k10 True Mycielski Graph 5 False c3mycieski False s13e False circulant_50_1_3 False s22e False difficult11 False Bull graph False Chvatal graph False Claw graph False Desargues Graph False Diamond Graph False Flower Snark False Frucht graph False Hoffman-Singleton graph False House Graph False Octahedron False Thomsen graph False Petersen graph True Pappus Graph True Grotzsch graph True Gray graph False Heawood graph False Herschel graph False Coxeter Graph False Brinkmann graph False Tutte-Coxeter graph False Tutte Graph False Robertson Graph False Folkman Graph False Balaban 10-cage False Pappus Graph True Tietze Graph False Sylvester Graph False Szekeres Snark Graph False Moebius-Kantor Graph False ryan False inp False c4c4 True regular_non_trans False bridge True p10k4 False c100 False starfish False c5k3 True k5pendant False Shrikhande graph False sylvester False fork False edge_critical_5 True edge_critical_11_1 False edge_critical_11_2 False pete_minus False c5 False bow_tie False pepper_residue_graph False barrus_graph False p5 False c6 False c9 False ce3 False ce4 False ce5 False k4e2split False flower_with_3_petals False flower_with_4_petals False paw_x_paw False Wagner Graph False houseX True ce7 False triangle_star False ce8 False ce9 False ce10 False p3 True binary_octahedron True ce11 True prism True ce12 False ce13 False IhCGGC_@? False alpha_critical_A_ True alpha_critical_Bw True alpha_critical_C~ False alpha_critical_Dhc False alpha_critical_D~{ False alpha_critical_E|OW True alpha_critical_E~~w True alpha_critical_FhCKG True alpha_critical_F~[KG False alpha_critical_FzEKW False alpha_critical_Fn[kG False alpha_critical_F~~~w True alpha_critical_GbL|TS False alpha_critical_G~?mvc False alpha_critical_GbMmvG False alpha_critical_Gb?kTG False alpha_critical_GzD{Vg False alpha_critical_Gb?kR_ False alpha_critical_GbqlZ_ True alpha_critical_GbilZ_ True alpha_critical_G~~~~{ True alpha_critical_GbDKPG False alpha_critical_HzCGKFo True alpha_critical_H~|wKF{ False alpha_critical_HnLk]My False alpha_critical_HhcWKF_ False alpha_critical_HhKWKF_ False alpha_critical_HhCW[F_ False alpha_critical_HxCw}V` False alpha_critical_HhcGKf_ False alpha_critical_HhKGKf_ False alpha_critical_Hh[gMEO True alpha_critical_HhdGKE[ True alpha_critical_HhcWKE[ True alpha_critical_HhdGKFK True alpha_critical_HhCGGE@ False alpha_critical_Hn[gGE@ True alpha_critical_Hn^zxU@ False alpha_critical_HlDKhEH True alpha_critical_H~~~~~~ False alpha_critical_HnKmH]N True alpha_critical_HnvzhEH False alpha_critical_HhfJGE@ True alpha_critical_HhdJGM@ True alpha_critical_Hj~KHeF True alpha_critical_HhdGHeB True alpha_critical_HhXg[EO True alpha_critical_HhGG]ES False alpha_critical_H~Gg]f{ True alpha_critical_H~?g]vs True alpha_critical_H~@w[Vs True alpha_critical_Hn_k[^o False

show(paw)

#NOTE: brendan mckay's nauty graph generation is built-in to Sage
#so we can call nauty with the appropriate wswitch to get connected graph
graphs.nauty_geng?

File: /projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/graphs/graph_generators.py
Signature : graphs.nauty_geng(self, options='', debug=False)
Docstring :
Returns a generator which creates graphs from nauty's geng program.

INPUT:

* "options" - a string passed to  geng  as if it was run at a
  system command line. At a minimum, you *must* pass the number of
  vertices you desire.  Sage expects the graphs to be in nauty's
  "graph6" format, do not set an option to change this default or
  results will be unpredictable.

* "debug" - default: "False" - if "True" the first line of geng's
  output to standard error is captured and the first call to the
  generator's "next()" function will return this line as a string.
  A line leading with ">A" indicates a successful initiation of the
  program with some information on the arguments, while a line
  beginning with ">E" indicates an error with the input.

The possible options, obtained as output of "geng --help":

        n    : the number of vertices
   mine:maxe : a range for the number of edges
               #:0 means '# or more' except in the case 0:0
     res/mod : only generate subset res out of subsets 0..mod-1

       -c    : only write connected graphs
       -C    : only write biconnected graphs
       -t    : only generate triangle-free graphs
       -f    : only generate 4-cycle-free graphs
       -b    : only generate bipartite graphs
                   (-t, -f and -b can be used in any combination)
       -m    : save memory at the expense of time (only makes a
                   difference in the absence of -b, -t, -f and n <= 28).
       -d#   : a lower bound for the minimum degree
       -D#   : a upper bound for the maximum degree
       -v    : display counts by number of edges
       -l    : canonically label output graphs

       -q    : suppress auxiliary output (except from -v)

Options which cause geng to use an output format different than the
graph6 format are not listed above (-u, -g, -s, -y, -h) as they
will confuse the creation of a Sage graph.  The res/mod option can
be useful when using the output in a routine run several times in
parallel.

OUTPUT:

A generator which will produce the graphs as Sage graphs. These
will be simple graphs: no loops, no multiple edges, no directed
edges.

See also: "Graph.is_strongly_regular()" -- tests whether a graph
  is strongly regular and/or returns its parameters.

EXAMPLES:

The generator can be used to construct graphs for testing, one at a
time (usually inside a loop).  Or it can be used to create an
entire list all at once if there is sufficient memory to contain
it.

   sage: gen = graphs.nauty_geng("2")
   sage: next(gen)
   Graph on 2 vertices
   sage: next(gen)
   Graph on 2 vertices
   sage: next(gen)
   Traceback (most recent call last):
   ...
   StopIteration: Exhausted list of graphs from nauty geng

A list of all graphs on 7 vertices.  This agrees with
https://oeis.org/A000088.

   sage: gen = graphs.nauty_geng("7")
   sage: len(list(gen))
   1044

A list of just the connected graphs on 7 vertices.  This agrees
with https://oeis.org/A001349.

   sage: gen = graphs.nauty_geng("7 -c")
   sage: len(list(gen))
   853

The "debug" switch can be used to examine geng's reaction to the
input in the "options" string.  We illustrate success. (A failure
will be a string beginning with ">E".)  Passing the "-q" switch to
geng will supress the indicator of a successful initiation.

   sage: gen = graphs.nauty_geng("4", debug=True)
   sage: print(next(gen))
   >A geng -d0D3 n=4 e=0-6

test = graphs.nauty_geng("4 -c")

for g in test:
    show(g)

#test conjecture[0] against all order 4 graphs
for g in graphs.nauty_geng("4 -c"):
    if conjs[0](g) == false:
        print g.graph6_string()
        show(g)
        break

CF

#regenerate the counterexample from g6 string
ce = Graph("CF")
show(ce)

#search for counterexamples among graphs with orders 7 thru 10
for i in [7..10]:
    for g in graphs.nauty_geng("{} -c".format(i)):
        if conjs[0](g) == false:
            print g.graph6_string()
            show(g)
            break

F??Fw

G???F{

H???CB~

I??????~w

#computer search for a counterexample to david's conjecture
david = lambda x: independence_number(x) <= x.order() - x.radius()

david(p3)

True

#search for counterexamples among graphs with orders 7 thru 10
for i in [11..12]:
    for g in graphs.nauty_geng("{} -c".format(i)):
        if david(g) == false:
            print g.graph6_string()
            show(g)
            break

paley101 = graphs.PaleyGraph(101)
paley101.show()

paley101.girth()

3

paley101.independent_set(value_only=True)

5

paley101.lovasz_theta()

10.049876

3+4

7

paley101.order()

101