#This code finds co-diamond-free and 2K_3+e-free connected graphs of order 9 without duplicate vertices which has no known existence of skew realization of rank<=4.
M=open(DATA+'GraphsOn9VerticesData.txt','U')
#It contains a co-diamond-free and 2K_3+e-free connected graph G of order 9 without duplicate vertices , then rank 4 skew realization S of its induced subgraph of order 8, then left null basis matrix N of S and then indices of minimal dependency columns of N.
V=[]
#V will contain graphs whose rank 4 skew realization is produced from 8 by 8 skew-symmetric matrix of rank<=4 stored in line 4i-2 of the input file
i=0
for line in M:
if(i % 4 ==1):
S=matrix(eval(line))
G = Graph()
H = Graph()
#A=matrix(1+S.ncols())
#A is 9 by 9 matrix whose principal 8 by 8 submatrix is the adjacency matrix of the graph of S.
for p in range(S.ncols()):
for q in range(S.ncols()):
if (S[p,q] !=0):
#A[p,q]=1
G.add_edge(p,q)
H.add_edge(p,q)
#Here G=H which is the graph of S.
if(i % 4 ==3):
smc=eval(line)
#smc=line.strip('\n')
w=Set([])
for j in range(len(smc)):
w=w+Set(smc[j])
#w is the union of indices of minimal dependent columns of Left Null space basis matrix of S
#print 'w=', w
for r in range(1+S.ncols()):
if (r in w):
#A[r,-1+A.ncols()]=1
#A[-1+A.ncols(),r]=1
G.add_edge(r,S.ncols())
#G becomes graph on vertices 0,1,...,8 obtained from H(=graph of S) by
#appending vertex 8 with N(8)=w, the union of minimal dependent columns of LNS basis matrix of S
if(S.rank()<=4):
V.append(G.graph6_string())
#The function nobarbell evaluated at a graph G returns true if G has no duplicate vertices and no induced 2K_3+e, otherwise it returns false.
def nobarbell(G):
A=G.adjacency_matrix()
n=G.order()
setn=[]
for i in range(n):
setn.append(i)
#print setn
#T is the set of all 6-subsets of row-indices
T=Subsets(setn,6,submultiset=True)
nodup=true
#Check for duplicate vertices
for i in range(-1+n):
for j in range(i+1,n):
if (G.neighbors(i)==G.neighbors(j)):
nodup=false
break
#If there are no duplicate vertices, then check each induced subgraph on 6 vertices to see if it is a 2K_3 +e
h=true
if (nodup):
m=0
while (m=4):
degree=false
C=B*B
D=B*C
#C=B^2, D=B^3. The following checks if G[B] has degree sum =14 and exactly two induced triangles.
# Note that (trace of B^2)=(sum of square of eigenvalues of B)=(degree sum of G[B]) and also
#(trace of B^3)=(sum of cube of eigenvalues of B)=6*(the number of induced triangles of G[B]).
if (degree and ((C.trace() == 14) and D.trace() == 12)):
h=false
#print '2K_3+e at', x
#G.show()
m=m+1
if(nodup==true and h==true):
return true
else:
return false