## July 5, 2018: Creativity through Computer algebra

The Blog entry Creativity through computer algebra illustrates how computer algebra projects can be creative. In the last part, I illustrate how one can come up with new questions.It mentions the square-graphs G(n) for which the vertices are the numbers 1 to n and where the edges are pairs (a,b) for which a+b is a square. One question which came out when experimenting with these graphs is that for n bigger or equal to 32, these graphs G(n) are Hamiltonian. The question was probed with the following code:

F[n_]:=Module[{e={}},Do[If[IntegerQ[Sqrt[x+y]], e=Append[e,x->y]],{x,n-1},{y,x+1,n}];e]; Puzzle[n_]:=FindHamiltonianCycle[UndirectedGraph[Graph[F[n]]]]; Do[If[Length[Puzzle[n]]>0,Print["G(",n,") is Hamiltonian"]],{n,1,152}]So, far we have checked that the graphs G(32), G(33),... G(151) are Hamiltonian. Here is a picture of the square graph G(151). So, far Mathematica gets stuck when checking whether G(152) is Hamiltonian. This illustrates that checking the Hamiltonian property is a hard problem. The actual paths look pretty random so that we also don't have a way to ``guess" the Hamiltonian path for larger n:

F[n_]:=Module[{e={}},Do[If[IntegerQ[Sqrt[x+y]],e=Append[e,x->y]],{x,n-1},{y,x+1,n}];e]; G[n_]:=Map[First,Flatten[First[FindHamiltonianCycle[UndirectedGraph[Graph[F[n]]]]]]]; ListPlot[G[151],Joined->True]I recently thought a bit about Hamiltonian graphs in in this project illustrated below. Unlike for general graphs, graphs which triangulate a manifold are Hamiltonian and the proof is constructive: