#all minimal planar push cliques on 6,7,8 vertices h6=Graph({0:[1,2,3,5], 1:[2,4], 2:[3,4], 3:[4], 4:[5]}) h7=Graph({0:[1,3,5], 1:[2,5], 2:[3,4], 3:[4], 4:[5]}) h8=Graph({0:[1,2,3,4,5], 1:[2,5], 2:[3], 3:[4], 4:[5]}) h9=Graph({0:[1,4,5], 1:[2,3,5], 2:[3,4], 3:[4], 4:[5]}) h10=Graph({0:[1,2,4,5,6], 1:[2,3], 2:[3,6], 3:[4,5], 4:[5], 5:[6]}) h11=Graph({0:[1,3,6], 1:[2,3,6], 2:[3,6], 3:[4,5], 4:[5,6], 5:[6]}) h12=Graph({0:[1,3,4,6], 1:[2,3,6], 2:[3,5], 3:[4], 4:[5], 5:[6]}) h13=Graph({0:[1,2,6,7], 1:[2,3,7], 2:[3,4], 3:[4,5], 4:[5,6], 5:[6,7], 6:[7]}) h14=Graph({0:[1,2,3,5,6,7], 1:[2,4], 2:[3,4], 3:[4], 4:[5,6,7], 5:[6], 6:[7]}) h15=Graph({0:[1,2,5,6,7], 1:[2,4], 2:[3,4,7], 3:[4,6,7], 4:[5,6], 5:[6], 6:[7]}) h16=Graph({0:[1,5,7], 1:[2,4,5,7], 2:[3,7], 3:[4,5,6,7], 4:[5], 5:[6], 6:[7]}) #property-checking functions def type1(g): return min(g.degree_sequence()) <= 2 def type2(g): return not g.is_hamiltonian() def type3(g): for u in g.vertices(): for v in g.vertices(): if u==v or g.has_edge(u,v): continue else: if len(set(g.neighbors(u)).intersection(g.neighbors(v))) <= 1: return True return False def type4(g): return (g.subgraph_search(h6) is not None) or (g.subgraph_search(h7) is not None) or (g.subgraph_search(h8) is not None) or (g.subgraph_search(h9) is not None) def type5(g): return (g.subgraph_search(h10) is not None) or (g.subgraph_search(h11) is not None) or (g.subgraph_search(h12) is not None) def type6(g): return (g.subgraph_search(h13) is not None) or (g.subgraph_search(h14) is not None) or (g.subgraph_search(h15) is not None) or (g.subgraph_search(h16) is not None) #main task n=6 all=graphs.nauty_geng("%d -c" % n) for g in all: if not g.is_planar(): continue if (not type1(g)) and (not type2(g)) and (not type3(g)) and (not type4(g)): g.show(layout="planar") n=7 all=graphs.nauty_geng("%d -c" % n) for g in all: if not g.is_planar(): continue if (not type1(g)) and (not type2(g)) and (not type3(g)) and (not type5(g)): g.show(layout="planar") n=8 all=graphs.nauty_geng("%d -c" % n) for g in all: if not g.is_planar(): continue if (not type1(g)) and (not type2(g)) and (not type3(g)) and (not type6(g)): g.show(layout="planar")
#base graphs h5=Graph({0:[1,3,4], 1:[2,4], 2:[3], 3:[4]}) h6=Graph({0:[1,2,3,5], 1:[2,4], 2:[3,4], 3:[4], 4:[5]}) h7=Graph({0:[1,3,5], 1:[2,5], 2:[3,4], 3:[4], 4:[5]}) h8=Graph({0:[1,2,3,4,5], 1:[2,5], 2:[3], 3:[4], 4:[5]}) h9=Graph({0:[1,4,5], 1:[2,3,5], 2:[3,4], 3:[4], 4:[5]}) h10=Graph({0:[1,2,4,5,6], 1:[2,3], 2:[3,6], 3:[4,5], 4:[5], 5:[6]}) h11=Graph({0:[1,3,6], 1:[2,3,6], 2:[3,6], 3:[4,5], 4:[5,6], 5:[6]}) h12=Graph({0:[1,3,4,6], 1:[2,3,6], 2:[3,5], 3:[4], 4:[5], 5:[6]}) h13=Graph({0:[1,2,6,7], 1:[2,3,7], 2:[3,4], 3:[4,5], 4:[5,6], 5:[6,7], 6:[7]}) h14=Graph({0:[1,2,3,5,6,7], 1:[2,4], 2:[3,4], 3:[4], 4:[5,6,7], 5:[6], 6:[7]}) h15=Graph({0:[1,2,5,6,7], 1:[2,4], 2:[3,4,7], 3:[4,6,7], 4:[5,6], 5:[6], 6:[7]}) h16=Graph({0:[1,5,7], 1:[2,4,5,7], 2:[3,7], 3:[4,5,6,7], 4:[5], 5:[6], 6:[7]}) #n=5 #bases=[h5] #n=6 #bases=[h6, h7, h8, h9] #n=7 #bases=[h10, h11, h12] n=8 bases=[h13, h14, h15, h16] good=[] for base in bases: good.append(base) all=graphs.nauty_geng("%d -c" % n) for g in all: #good vertex-connectivity? if g.vertex_connectivity() < 2: continue #planarity? if not g.is_planar(): continue #is base? is_base=False for base in bases: if g.is_isomorphic(base): is_base=True break if is_base: continue #main task found=False for base in bases: if g.subgraph_search(base) is not None: found=True break if found: good.append(g) #display all for g in good: is_base=False for base in bases: if g.is_isomorphic(base): is_base=True break if is_base: c='#FF9900' else: c='#00FF00' g.show(layout="planar", vertex_color=c)