#OK to post
#Soham Palande, Assignment 18, 11/15/2020



#PART 1

#AllKcomponentsGraphs(n,k): The set of all connected (labeled) graphs with k #components on {1,..,n}
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(n,k): The first N terms of the sequence "number of connected (labeled) graphs with n vertices", by BRUTE force
NuKcomponentsGraphs:=proc(N,k) local n1:
[seq( nops(AllKcomponentsGraphs(n1,k)),n1=1..N)]:
end:


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


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


#Yes the sequences are in the OEIS. 

NuKcomponentsGraphs(5,2)
A323875

NuKcomponentsGraphs(5,3)
A323876



#PART 2


AveNuCC:=proc(n,K,M) local sum,G,avg,i:
sum:=0:
avg:=0:
for i from 1 to M do
    G:=RandGr(n,K):
    sum:=sum+nops(CCs(G)):
od:
avg:=sum/M:
end:


#The numbers seem pretty consistent for fixed values of K (# of edges) as well

seq(evalf(AveNuCC(30,10,1000)),n=1..10)

[20.04400000, 20.03900000, 20.05900000, 20.05300000, 20.04900000, 20.04400000, 20.05400000, 20.04800000, 20.05400000, 20.03900000]

#Hence M=1000 is a suitable value.

seq(evalf(AveNuCC(30,k,1000)),k=0..10)
30., 29., 28., 27., 26., 25.00700000, 24.00900000, 23.01300000, 22.02400000, 21.03400000, 20.05500000

#Seems to work for different values of K which are the number of edges in the graph. For example a graph with n=30 and 1 edge will #have 29 connected components


#PART 3


#A graph with n vertices must have at least n-1 edges to be connected. So we iterate from n-1 to nC2

EstimateCutOff:=proc(n,M) local max,i:
max:=binomial(n,2):
for i from n-1 to max do:
    if (AveNuCC(n,i,M)<1.05) then:
           break;
    fi:
od:
i:
end:

#Example - took a long time to compute

EstimateCutOff(30,1000) 
84



#PART 5

Prove: A graph in n vertices has no cycles iff it is connected and has n-1 edges.

Let us consider a graph G which is connected and has n-1 edges. Then by definition since G is both connected with order n and size n-1, then G is a tree. Trees are by definition acyclic and hence do not have cycles. Hence G has no cycles.