#OK to post homework
#Salman Manzoor 02-23-2025, Assignment 9

with(combinat):

#1
CheegerC:=proc(G) local N,n,E,cons,range,i,c,C,S,s,dS,target,k:
n:=G[1]: 
E:=G[2]:
range:=floor(n/2):
cons:=-1:
N:={seq(i,i=1..n)}:
for i from 1 to range do
	S:=choose(N,i):
	for s in S do
		C:=N minus s:
		target:={seq(seq({c,k},c in C),k in s)}:
		dS:=nops(E intersect target):
		if (cons=-1) then cons:=dS/i: next: fi:
		cons:=min(dS/i,cons):
	od:
od:
cons:
end:

#2
CheckBounds:=proc(G) local c,L,B:
c:=CheegerC(G): L:=lam2(G):
B:=[(L[1]-L[2])/2,sqrt(2*L[1]*(L[1]-L[2]))]:
[c,B,evalb(c>=B[1] and B[2]>=c)]:
end:

#the results from 
#seq(CheegerC(Gnd(n, 2)), n = 5 .. 10) and
#seq(CheegerC(Gnd(n, 3)), n = 5 .. 10)
#are as expected