# Revision history [back]

g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
for g in g10:
if g.subgraph_search(H,induced=False):
g.show()


After defining the subgraph you want, the cycle on 5 vertices, look through the graphs in g10 and figure out if it has H, not necessarily induced. It then prints out the graphs.

g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
for g in g10:
if g.subgraph_search(H,induced=False):
g.show()


After defining the subgraph you want, the cycle on 5 vertices, look through the graphs in g10 and figure out if it has H, not necessarily induced. It then prints out the graphs.graphs. The documentation for subgraph_search is here

g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
for g in g10:
if g.subgraph_search(H,induced=False):
g.show()


After defining the subgraph you want, the cycle on 5 vertices, look through the graphs in g10 and figure out if it has H, not necessarily induced. It then prints out the graphs. The documentation for subgraph_search is here.

With respect to your comment below, I think that it is possible but I don't know enough of the intricacies of the graph theory commands. Consider this code.

g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
K = graphs.CompleteGraph(4)
for g in g10:
if g.subgraph_search(H,induced=False):
for p in g.subgraph_search_iterator(K,induced=True):
for v in p:
if g.degree(v)<6:
print "False"
print p
g.show()
else:
print "True"


For each graph in g10 it looks for a non-induced C_5. If the graph has it then it looks for an induced K_4. When it finds it, it looks at all the vertices in it (the subgraph p which is a K_4) and looks to see if the degree of any vertex is less than 6. If so, it prints out "False", the 4 vertices inducing K_4 and the graph from g10 that they are a subgraph of. If you didn't require the graph to have H then you can easily modify the code to what you want.

g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
for g in g10:
if g.subgraph_search(H,induced=False):
g.show()


After defining the subgraph you want, the cycle on 5 vertices, look through the graphs in g10 and figure out if it has H, not necessarily induced. It then prints out the graphs. The documentation for subgraph_search is here.

EDIT: With respect to your comment below, I think that it is possible but I don't know enough of the intricacies of the graph theory commands. Consider this code.

g10=[g for g in graphs.nauty_geng('10 25') if g.clique_number()==4]
H = graphs.CycleGraph(5)
K = graphs.CompleteGraph(4)
for g in g10:
if g.subgraph_search(H,induced=False):
for p in g.subgraph_search_iterator(K,induced=True):
for v in p:
if g.degree(v)<6:
print "False"
print p
g.show()
else:
print "True"


For each graph in g10 it looks for a non-induced C_5. If the graph has it then it looks for an induced K_4. When it finds it, it looks at all the vertices in it (the subgraph p which is a K_4) and looks to see if the degree of any vertex is less than 6. If so, it prints out "False", the 4 vertices inducing K_4 and the graph from g10 that they are a subgraph of. If you didn't require the graph to have H then you can easily modify the code to what you want.