#This SAGE code verifies that there are no connected co-diamond-free and 2K_3+e-free connected graphs of order n= 8 without duplicate vertices and \
#minimum rank more than 4. It has as input the text file connectedgraphs8.txt which contains all connected graphs on 8 vertices in graph6 format, and \
#Skew-Realizations8.txt which contains a list of graphs on 8 vertices and realizations. We note that the same code works for n=6,7 by changing the file names #appropriately.\
\
\
\
#===============================================================================================================\
#the function nocodiamond evaluated at a graph G returns true if G has no induced co-diamond, otherwise it returns false\
def nocodiamond(G):\
A=G.adjacency_matrix()\
n=G.order()\
setn=[]\
for i in range(n):\
setn.append(i)\
#print setn\
\
S=Subsets(setn,4,submultiset=True)\
#T=Subsets(setn,6,submultiset=True)\
\
h=true\
k=0\
while (k=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\
#=========================================================================================================== \
#=========================================================================================================== \
\
# The code below is for n=8. It starts with McKay\'92s list, connectedgraphs8.txt, of connected graphs on 8 vertices, \
#and produces a list V of those that are co-diamond and 2K_3+e free without duplicate vertices.\
#We check this list against the graphs of the rank 4 matrices in SkewRealizations8.txt, and verify that \
#each matrix in the list has rank 4 and that the set of graphs are the same.\
f=open(DATA+'connectedgraphs8.txt','U')\
#For connected graphs of order 6, 7 connectedgraphs6.txt, connectedgraphs7.txt, respectively\
\
\
V=[]\
#V will contain co-diamond-free and 2K_3+e-free connected graphs of order n without duplicate vertices\
for line in f:\
G=Graph(line)\
A=G.adjacency_matrix()\
n=G.order() \
\
if (nocodiamond(G) and nobarbell(G)):\
V.append(line)\
\
\
M=open(DATA+\'92SkewRealizations8.txt','U')\
#For graphs of order 6, 7 use SkewRealizations6.txt, SkewRealizations7.txt respectively\
\
U=[]\
#U will contain graphs whose rank 4 skew realization is stored in odd numbered lines of the preceding input file \
i=0\
for line in M:\
if(i % 2 ==1):\
S=matrix(eval(line)) \
A=matrix(S.ncols())\
for p in range(S.ncols()):\
for q in range(S.ncols()):\
if (S[p,q] !=0):\
A[p,q]=1\
else: \
A[p,q]=0 \
G=Graph(A)\
if(S.rank()<=4):\
U.append(G.graph6_string())\
i=i+1 \
\
Unknown=[]\
for p in range(len(V)):\
GV=Graph(V[p])\
GU=Graph(U[p])\
if (not(GV.is_isomorphic(GU))):\
Unknown.append(V[p]) \
if (len(Unknown)==0):\
print(\'91All graphs of order\'94,n,\'92have a rank 4 realization\'92)\
else:\
print(\'91The following graphs of order\'94,n, \'91do not have a known realization of rank 4:\\n\'92) \
print (\'91They are following:\\n\'92)\
for t in range(len(Unknown)):\
print Unknown[t].strip('\\n')\
\
}