#  This page contains some Maple codes to help the reader to verify some of the calculations of the paper "Quartic graphs with minimum spectral gap."
#
#Lemma 3.6:
restart:
solve({(mu-4)*x[1]=-2*x[1]-2*x[2], (mu-4)*x[2]=-3*x[1]-x[3],(mu-4)*x[3]=-x[2]-x[3]-2*x[4]},{x[2],x[3],x[4]}): 
solve({mu*z[1]=z[1]-z[2],(mu-4)*z[2]=-2*z[1]-2*z[3],(mu-4)*z[3]=-2*z[2]-z[3]-x[4]},{z[1],z[2],z[3]}): 
x[2] := -(1/2)*mu*x[1]+x[1]: 
x[3] := (1/2)*x[1]*(mu^2-6*mu+2): 
x[4] := -(1/4)*x[1]*(mu^3-9*mu^2+19*mu-4):
z[1] := x[1]*(mu^3-9*mu^2+19*mu-4)/(2*mu^3-16*mu^2+26*mu-4): 
z[2] := -(mu-1)*x[1]*(mu^3-9*mu^2+19*mu-4)/(2*mu^3-16*mu^2+26*mu-4):
z[3] := (mu^2-5*mu+2)*x[1]*(mu^3-9*mu^2+19*mu-4)/(4*mu^3-32*mu^2+52*mu-8):
delta := simplify(4*z[1]+2*z[2]+2*z[3]-3*x[1]-2*x[2]-2*x[3]-x[4]):
#N := ||x'||^2  &  M := X'L(gamma')X'^T
N := simplify(1+4*(z[1])^2+2*(z[2])^2+2*(z[3])^2-3*(x[1])^2-2*(x[2])^2-2*(x[3])^2-(x[4])^2):
M := simplify(4*(z[1]-z[2])^2+4*(z[2]-z[3])^2+2*(z[3]-x[4])^2-6*(x[1]-x[2])^2-2*(x[2]-x[3])^2-4*(x[3]-x[4])^2+mu):
simplify((M-(N-(delta^2/n))*mu));
{(n+1)*mu^6+(-17*n-19)*mu^5+(104*n+132)*mu^4+(-275*n-399)*mu^3+(297*n+475)*mu^2+(-90*n-150)*mu+8*n=
collect((n+1)*mu^6+(-17*n-19)*mu^5+(104*n+132)*mu^4+(-275*n-399)*mu^3+(297*n+475)*mu^2+(-90*n-150)*mu+8*n,n)};
p[1] := t^6-17*t^5+104*t^4-275*t^3+297*t^2-90*t+8:
p[2] := t^6-19*t^5+132*t^4-399*t^3+475*t^2-150*t:
p[3] := (t-5)*(t^3-8*t^2+14*t-5)*(t-6):
p[4] := 18*p[1]+p[2]:
{t^3-8*t^2+14*t-5, fsolve({t^3-8*t^2+14*t-5=0})};
{'p[1]', fsolve({p[1]=0})};
{'p[4]', fsolve({p[4]=0})};

#Lemma 3.10 (i):
restart:
f:=(x,y)-> (2*(3*x-mu*x+2*y))/(mu^2-7*mu+10): g:=(x,y)-> (2*(x-mu*y+4*y))/(mu^2-7*mu+10):
x[r+1] := f(x[r],x[r+3]):
x[r+2] := g(x[r],x[r+3]):
z[r+1] := g(x[r+3],x[r]):
z[r+2] := f(x[r+3],x[r]):
delta := 2*z[r+1]+z[r+2]-x[r+1]-2*x[r+2]:
h := 2*(x[r]-x[r+1])^2+2*(x[r+1]-x[r+2])^2+4*(x[r+2]-x[r+3])^2:
hprime := 4*(x[r]-z[r+1])^2+2*(z[r+1]-z[r+2])^2+2*(z[r+2]-x[r+3])^2:
epsilon := 2*(z[r+1])^2+(z[r+2])^2-(x[r+1])^2-2*(x[r+2])^2-(delta^2/n):
simplify(hprime-h-epsilon*mu); 

#Lemma 3.10 (ii):
restart:
f:=(x,y)-> (2*(-mu^2*x+7*mu*x+mu*y-10*x-6*y))/(mu^3-11*mu^2+36*mu-32):
g:=(x,y)-> (-mu*y+2*x+6*y)/(mu^2-7*mu+8):
l:=(x,y)-> (2*(-mu^2*y+8*mu*y-2*x-14*y))/(mu^3-11*mu^2+36*mu-32):
x[r+1] := f(x[r],x[r+4]):
x[r+2] := g(x[r],x[r+4]):
x[r+3] := l(x[r],x[r+4]):
z[r+1] := l(x[r+4],x[r]): 
z[r+2] := g(x[r+4],x[r]): 
z[r+3] := f(x[r+4],x[r]):
delta := z[r+1]+2*z[r+2]+z[r+3]-x[r+1]-2*x[r+2]-x[r+3]:
h := 2*(x[r]-x[r+1])^2+2*(x[r+1]-x[r+2])^2+2*(x[r+2]-x[r+3])^2+2*(x[r+3]-x[r+4])^2+2*(x[r+2]-x[r+4])^2:
hprime := 2*(x[r]-z[r+1])^2+2*(x[r]-z[r+2])^2+2*(z[r+1]-z[r+2])^2+2*(z[r+2]-z[r+3])^2+2*(z[r+3]-x[r+4])^2:
epsilon := (z[r+1])^2+2*(z[r+2])^2+(z[r+3])^2-(x[r+1])^2-2*(x[r+2])^2-(x[r+3])^2-(delta^2/n):
simplify(hprime-h-epsilon*mu);
Phi:=collect(n*(x[r]+x[r+4])*mu^2+((-7*x[r]-7*x[r+4])*n+2*x[r]-2*x[r+4])*mu+(8*x[r]+8*x[r+4])*n-12*x[r]+12*x[r+4],n);

#Lemma 3.10 (iii):
restart:
f:=(x,y)-> -(2*(mu^2*x-6*mu*x+5*x+2*y))/(mu^3-10*mu^2+27*mu-14):
g:=(x,y)->  (2*(mu*x+mu*y-3*x-4*y))/(mu^3-10*mu^2+27*mu-14):
l:=(x,y)-> -(mu^2*y-7*mu*y+4*x+10*y)/(mu^3-10*mu^2+27*mu-14):
x[r+1] := f(x[r],x[r+4]):
x[r+2] := g(x[r],x[r+4]):
x[r+3] := l(x[r],x[r+4]):
z[r+1] := l(x[r+4],x[r]):
z[r+2] := g(x[r+4],x[r]):
z[r+3] := f(x[r+4],x[r]):
delta := 2*z[r+1]+2*z[r+2]+z[r+3]-x[r+1]-2*x[r+2]-2*x[r+3]:
h := 2*(x[r]-x[r+1])^2+2*(x[r+1]-x[r+2])^2+2*(x[r+2]-x[r+3])^2+2*(x[r+3]-x[r+4])^2+2*(x[r+2]-x[r+3])^2:
hprime := 2*(x[r]-z[r+1])^2+4*(z[r+1]-z[r+2])^2+2*(z[r+2]-z[r+3])^2+2*(z[r+3]-x[r+4])^2:
epsilon := 2*(z[r+1])^2+2*(z[r+2])^2+(z[r+3])^2-(x[r+1])^2-2*(x[r+2])^2-2*(x[r+3])^2-(delta^2/n):
simplify(hprime-h-epsilon*mu);
Phi := collect(n*(x[r]+x[r+4])*mu^3-10*n*(x[r]+x[r+4])*mu^2+((27*x[r]+27*x[r+4])*n-2*x[r]+2*x[r+4])*mu+(-14*x[r]-14*x[r+4])*n+10*x[r]-10*x[r+4],n);
{t^3-10*t^2+27*t-4, fsolve({t^3-10*t^2+27*t-4=0})};

#Lemma 3.12 (i):
restart:
f:=(x,y)-> -(2*(mu^3*x-11*mu^2*x+36*mu*x+mu*y-32*x-6*y))/(mu^4-14*mu^3+67*mu^2-126*mu+76):
g:=(x,y)->  (2*(2*mu^2*x+mu^2*y-14*mu*x-9*mu*y+20*x+18*y))/(mu^4-14*mu^3+67*mu^2-126*mu+76):
l:=(x,y)-> -(mu^3*y-13*mu^2*y+4*mu*x+52*mu*y-16*x-60*y)/(mu^4-14*mu^3+67*mu^2-126*mu+76):
p:=(x,y)->  (2*(-mu^3*y+11*mu^2*y-36*mu*y+4*x+34*y))/(mu^4-14*mu^3+67*mu^2-126*mu+76):
x[r+1] := f(x[r],x[r+5]):
x[r+2] := g(x[r],x[r+5]):
x[r+3] := l(x[r],x[r+5]):
x[r+4] := p(x[r],x[r+5]):
z[r+1] := p(x[r+5],x[r]):
z[r+2] := l(x[r+5],x[r]):
z[r+3] := g(x[r+5],x[r]):
z[r+4] := f(x[r+5],x[r]):
delta := z[r+1]+2*z[r+2]+z[r+3]+2*z[r+4]-2*x[r+1]-x[r+2]-2*x[r+3]-x[r+4]:
h := 4*(x[r]-x[r+1])^2+2*(x[r+1]-x[r+2])^2+2*(x[r+2]-x[r+3])^2+2*(x[r+3]-x[r+4])^2+2*(x[r+4]-x[r+5])^2+2*(x[r+3]-x[r+5])^2:
hprime:=2*(x[r]-z[r+1])^2+2*(x[r]-z[r+2])^2+2*(z[r+1]-z[r+2])^2+2*(z[r+2]-z[r+3])^2+2*(z[r+3]-z[r+4])^2+4*(z[r+4]-x[r+5])^2:
epsilon := (z[r+1])^2+2*(z[r+2])^2+(z[r+3])^2+2*(z[r+4])^2-2*(x[r+1])^2-(x[r+2])^2-2*(x[r+3])^2-(x[r+4])^2-(delta^2/n):
simplify(hprime-h-epsilon*mu);
Phi:=collect((n*(x[r]+x[r+5])*mu^4-14*n*(x[r]+x[r+5])*mu^3+((67*x[r]+67*x[r+5])*n-2*x[r]+2*x[r+5])*mu^2+((-126*x[r]-126*x[r+5])*n+18*x[r]-18*x[r+5])*mu+(76*x[r]+76*x[r+5])*n-40*x[r]+40*x[r+5]),n);
{t^4-14*t^3+67*t^2-126*t+46,  fsolve({t^4-14*t^3+67*t^2-126*t+46=0})};

#Lemma 3.12 (ii):
restart:
x[2] := -(1/2)*mu*x[1]+x[1]:
x[3] := (1/2)*x[1]*mu^2-3*mu*x[1]+x[1]:
x[4] := -(1/4)*(mu^3-10*mu^2+24*mu-4)*x[1]:
x[5] := -x[1]*(mu^4-14*mu^3+62*mu^2-88*mu+12)/(2*mu-12):
x[6] := x[1]*(mu^5-17*mu^4+102*mu^3-252*mu^2+216*mu-24)/(4*mu-24):
omega := (mu^5-17*mu^4+102*mu^3-252*mu^2+216*mu-24)/(mu^5-17*mu^4+103*mu^3-261*mu^2+238*mu-24):
z[1] := omega*x[1]: z[2]:=omega*(1-mu)*x[1]: z[3]:=omega*(mu^2-4*mu+1)*x[1]: z[4]:=-(omega*(mu^3-8*mu^2+15*mu-2)*x[1])/2:
delta := 4*z[1]+2*z[2]+z[3]+2*z[4]-3*x[1]-2*x[2]-x[3]-2*x[4]-x[5]:
N := 1+4*(z[1])^2+2*(z[2])^2+(z[3])^2+2*(z[4])^2-3*(x[1])^2-2*(x[2])^2-(x[3])^2-2*(x[4])^2-(x[5])^2:
M := mu+4*(z[1]-z[2])^2+2*(z[2]-z[3])^2+2*(z[3]-z[4])^2+4*(z[4]-x[6])^2-4*(x[1]-x[2])^2-2*(x[1]-x[2])^2-2*(x[2]-x[3])^2          -2*(x[3]-x[4])^2-2*(x[4]-x[5])^2-2*(x[5]-x[6])^2-2*(x[4]-x[6])^2:
simplify((M-(N-(delta^2/n))*mu));
Phi := collect(mu^9*n-28*mu^8*n+(326*n+2)*mu^7+(-2042*n-46)*mu^6+(7429*n+418)*mu^5+(-15770*n-1886)*mu^4+(18492*n+4296)*mu^3+(-10320*n-4280)*mu^2+(1800*n+1000)*mu-96*n,n);
n:=21: 
{mu^5-18*mu^4+119*mu^3-348*mu^2+408*mu-100, fsolve({mu^5-18*mu^4+119*mu^3-348*mu^2+408*mu-100=0})};
{Phi, fsolve({Phi=0})};

#Lemma 3.12 (iii):
restart:
omega := 1/(mu^7-24*mu^6+231*mu^5-1136*mu^4+2996*mu^3-4012*mu^2+2200*mu-168):
x[1] := -4*(2*mu^2-19*mu+42)*omega*x[8]:
x[2] := (2*(mu-6))*(mu^2-7*mu+14)*omega*x[8]:
x[3] := 4*(mu^3-12*mu^2+43*mu-42)*omega*x[8]:
x[4] := -2*(mu^4-16*mu^3+87*mu^2-176*mu+84)*omega*x[8]:
x[5] := 2*(mu^5-19*mu^4+132*mu^3-400*mu^2+470*mu-84)*omega*x[8]:
x[6] := -(mu^6-23*mu^5+206*mu^4-896*mu^3+1896*mu^2-1612*mu+168)*omega*x[8]:
x[7] := -2*(mu^6-21*mu^5+170*mu^4-662*mu^3+1244*mu^2-932*mu+84)*omega*x[8]:
omegaprime := 1/(mu^5-15*mu^4+77*mu^3-157*mu^2+110*mu-8):
z[1] := -8*omegaprime*x[8]:
z[2] := 8*(mu-1)*omegaprime*x[8]:
z[3] := -4*(mu^2-5*mu+2)*omegaprime*x[8]:
z[4] := 4*(mu^3-8*mu^2+13*mu-2)*omegaprime*x[8]:
z[5] := -2*(mu^4-12*mu^3+43*mu^2-44*mu+4)*omegaprime*x[8]:
delta := 4*z[1]+2*z[2]+2*z[3]+z[4]+2*z[5]-2*x[1]-2*x[2]-x[3]-2*x[4]-x[5]-2*x[6]-x[7]: 
N := 1+4*(z[1])^2+2*(z[2])^2+2*(z[3])^2+(z[4])^2+2*(z[5])^2-2*(x[1])^2-2*(x[2])^2-(x[3])^2-2*(x[4])^2-(x[5])^2-2*(x[6])^2-       (x[7])^2:
M := mu+4*(z[1]-z[2])^2+4*(z[2]-z[3])^2+2*(z[3]-z[4])^2+2*(z[4]-z[5])^2+4*(z[5]-x[8])^2-4*(x[1]-x[2])^2-2*(x[1]-x[3])^2-2*  (x[2]-x[4])^2-2*(x[3]-x[4])^2-2*(x[4]-x[5])^2-2*(x[5]-x[6])^2-2*(x[6]-x[7])^2-2*(x[6]-x[8])^2-2*(x[7]-x[8])^2:
simplify((M-(N-(delta^2/n))*mu));
mu^12*n-39*mu^11*n+(668*n+2)*mu^10+(-6606*n-68)*mu^9+(41701*n+992)*mu^8+(-175339*n-8100)*mu^7+(497026*n+40446)*mu^6+(-939272*n-126432)*mu^5+(1140452*n+242312)*mu^4+(-823624*n-264520)*mu^3+(300472*n+137816)*mu^2+(-36080*n-20208)*mu+1344*n=
collect(mu^12*n-39*mu^11*n+(668*n+2)*mu^10+(-6606*n-68)*mu^9+(41701*n+992)*mu^8+(-175339*n-8100)*mu^7+(497026*n+40446)*mu^6+(-939272*n-126432)*mu^5+(1140452*n+242312)*mu^4+(-823624*n-264520)*mu^3+(300472*n+137816)*mu^2+(-36080*n-20208)*mu+1344*n,n);
p[1]:=t^12-39*t^11+668*t^10-6606*t^9+41701*t^8-175339*t^7+497026*t^6-939272*t^5+1140452*t^4-823624*t^3+300472*t^2-36080*t+1344:
p[2]:=2*t^10-68*t^9+992*t^8-8100*t^7+40446*t^6-126432*t^5+242312*t^4-264520*t^3+137816*t^2-20208*t:
p[3]:=t^8-28*t^7+328*t^6-2082*t^5+7731*t^4-16830*t^3+20176*t^2-11204*t+1684:
p[4]:=simplify(p[1]*n+p[2]):
n := 26:
{'p[1]',  fsolve({p[1]=0})};
{'p[3]',  fsolve({p[3]=0})};
{'p[4]',  fsolve({p[4]=0})};