read(`C11.txt`):


# uses MinMaxNNpablo to compute the independence number of a graph G=[n,E]
IndNu:=proc(G) local i:
 i:=1:
 while (i+1<=G[1]) and MinMaxNNpablo(G,i+1)=0 do:
  i++:
 od:
 i:
end:

###################################
# CHALLENGE: 
# The independence number of Gnd is floor(n/(d+1))
#
# Proof: 
# Observe that Gnd is the d-th power graph of the C_n (the cycle graph on n vertices).
# In particular, finding the independence number is the same as finding the maximum number
# of vertices on C_n which are distance > d. We can achieve this greedily by taking
# {1,1+(d+1),1+2(d+1),...,1+k(d+1)} where k is max such that (n+1)-(1+k(d+1)) >= d+1. Note that k+1
# will be the independence number. We obtain the condition k+1<= n/(d+1)
# Since k+1 must be an integer, the bound is equivalent to k+1<= floor(n/(d+1)). QED.
###################################

#####
# UpperBoundMinMaxNN(Ck(8),129,5000) = 7.
#####
UpperBoundMinMaxNN:= proc(G,r,K) local mini,V,H,i,curr:
 V:={seq(i,i=1..G[1])}:
 H:=randcomb(V,r):
 mini:=MaxNN(G,H):
 for i from 2 to K do:
  H:=randcomb(V,r):
  curr:= MaxNN(G,H):
  if curr < mini then:
   mini:=curr:
  fi:
 od:

 mini:
end: