#OK to post homework
#Kent Mei, 11/15/20, Assignment 18

#---------------------------------
#Part 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(AllKcomponentsGraphs(n1,K)), n1=1..N)]:

end:

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

#I'm assuming NuConGgen is supposed to be NuKcomponentsGraphs
#NuKcomponentsGraphs(5,2) = [0, 1, 3, 19, 230]
#Yes, it is A323875.

#NuKcomponentsGraphs(5,3) = [0, 0, 1, 6, 55]
#Yes, it is A323876.

#---------------------------------
#Part 2

AveNuCC:=proc(n,K,M) local i, L, sum:

sum:=0:

for i from 1 to M do
	sum = sum + nops(CCs(RandGr(n,K))):
od:

evalf(sum / M):

end:

#Trials of AveNuCC(30,29,1000):
#5.622
#5.523
#5.638
#5.567
#5.59
#M=1000 seems to get relatively close answers, differing from one another by around 0.1 at most.

#AveNuCC(30,29,5000)
#5.5914
#5.6048
#5.588

#Clearly, higher values of N like N=5000 allows for more reliable results. However, since we're working with number of connected components which is an integer,  I think having the average vary by ~0.1 is fine.


#---------------------------------
#Part 3

EstimateCutOff:=proc(n,M) local ave, K:

K := n-2:
ave := 2:

while ave > 1.05 do
	K := K + 1:
	ave := AveNuCC(n,K,M):
od:

K:

end:


#---------------------------------
#Part 4

#Optional, I don't think the virtual computer lab can handle such large values of n and M.


#---------------------------------
#Part 5

#Optional

#I don't think it's necessarily true that if a graph in n vertices has no cycles that it is connected and has exactly n-1 edges because for example you can have a graph of say 3 nodes with 0 edges and it would be a graph that has no cycles.
#I think the proper statement to prove would be that a graph in n vertices with no cycles is connected if and only if it has exactly n-1 edges.

# => Suppose we have a connected graph in n vertices with no cycles. We prove that it has exactly n-1 edges by induction.
#	Base case: a connected graph with 1 vertex with no cycles has 0 edges.
# 	Assume that all connected graphs in k vertices with no cycles have k-1 edges.
#   We need to prove all connected graph in k+1 vertices with no cycle have k edges.
#   If we have a graph with k vertices with no cycles with k - 1 edges, it only takes 1 edge to connect the k+1th vertex to that graph, thus showing we can form a connected graph in k+1 vertices with no cycles with k edges.
#	Therefore, by induction, we have shown that a connected graph in n vertices with no cycles has n-1 edges.

# <= Suppose we have a graph in n vertices with no cycles with exactly n - 1 edges. We need to show it is connected.
# 	Assume to the contrary that G is disconnected. Then, we can find that G has (at least) 2 components, G1, G2 where each component also has no cycles. If we pick a vertex u in G1 and vertex v in G2 and create a new edge between u and v, we end up with a connected graph of n vertices with n edges and still no cycles. However, this contradicts the fact that a connected graph in n vertices with no cycles must have n-1 edges. So, it must be the case that G is connected.