#OK to post homework
#Tianyi Liu, Nov15, Assignment 18
1.
AllKcomponentsGraphs:=proc(n,k) local S,s,C:
S:=AllGraphs(n):
C:={}:

for s in S do
 if nops(CCs(s))=k then
  C:=C union {s}:
 fi:
od:

C:
end:

NuKcomponentsGraphs:=proc(N,K) local n1:
[seq( nops(AllKcomponentsGraph(n1,K)),n1=1..N)]:
end:

NuKcomponentsGraphs(6,1) = [1, 1, 4, 38, 728, 26704]
NuConG(6) = [1, 1, 4, 38, 728, 26704]

NuKcomponentsGraphs(5,2) = [0, 1, 3, 19, 230]
A323875

NuKcomponentsGraphs(5,3) = [0, 0, 1, 6, 55]
A323876

2.
AveNuCC:=proc(n,K,M) local sum,i:
sum:=0:
for i from 1 to M do
 sum:=sum+nops(CCs(RandGr(n,K)))
od:
sum/M:
end:
 
evalf(AveNuCC(30,35,1000))
3.77
3.722
3.685
3.795
The averages are pretty close within in 0.1 of difference. As M gets larger, averages will get closer.

3.
EstimateCutOff:=proc(n,M) local i:
for i from 1 to binomial(n,2) do
 if AveNuCC(n,i,M) <= 1.05 then
  RETURN(i):
 fi:
od:
end: