#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())
#Gc=G.canonical_label()
#print G.graph6_string()
#G.set_pos(G.get_pos())
#G.show(save_pos=True)
#print 'Can verify that N(8)=', w
#G.delete_vertex(8)
#H.set_pos(G.get_pos())
#H.show()
i=i+1
#print 'V=', V
#Now V contains graphs of order 9 whose rank 4 skew realization exists
Unknown=[]
#Unknown will contain connected graphs of order 9 without any known rank 4 realization
f=open(DATA+'pot9output.txt','U')
#pot9output.txt contains all co-diamond-free, 2K_3+e-free connected graphs of order 9 with no duplicate vertices
j=0
for p in f:
GU=Graph(p)
realization=false
GV=Graph(V[j])
if(GU.is_isomorphic(GV)):
realization=true
j=j+1
if(realization==false):
Unknown.append(p)
print 'Total number of connected graphs of order 9 without known rank 4 realization is' , len(Unknown), '\n'
print 'They are following:\n'
for t in range(len(Unknown)):
print Unknown[t].strip('\n')