# hw 9 - Pablo Blanco
# OK to post.
with(combinat):
read(`C9.txt`): #C9.txt should be included in the same folder

#
CheegerC:=proc(G) local S,n,e,E,i,j,V,C,edgco,mini:
 n:=G[1]:
 E:=G[2]:
 V:={seq(i,i=1..n)}: # the set of vertices
 mini:=infinity: # current minimum for Cheeger constant

 for j from 1 to floor(n/2) do:
  C:=choose(V,j): # S is a set of size i
  for S in C do:
   edgco:=0: # counts the number of edges coming out of S
   for e in E do:
    if member(e[1],S) and not(member(e[2],S)) then:
     edgco++:
    fi:
    if member(e[2],S) and not(member(e[1],S)) then:
     edgco++:
    fi:
   od:
   if edgco/j < mini then:
    mini:=edgco/j:
   fi:
  od:
 od:
 
 mini:
end:

# 
CheckBounds:=proc(G) local lam,d,l2,booly,cheeg:
 lam:=lam2(G):
 if lam2 = FAIL then:
  error"The given graph is not regular.":
 fi:
 d:=lam[1]: 
 l2:=lam[2]:
 cheeg:=CheegerC(G):
 booly:=evalb(cheeg >=(d-l2)/2 and cheeg<=sqrt(2*d*(d-l2)) ): 
 cheeg, [(d-l2)/2,sqrt(2*d*(d-l2))],booly:
end:

# results of CheckBounds Gnd
# They are all within the bounds!