Edit: I made a mistake with some of the language here. A comment from a true graph theorist:

“Hamiltonian” usually means there’s a hamilton/hamiltonian cycle. Graphs with a hamilton path are “traceable”. Hamiltonian implies traceable, but not conversely.

Thus, I have edited below accordingly.

——————————-

There was a nice video up on Numberphile about a problem which could easily be explained to a school student, and yet we don’t yet know the answer to it. See the videos here:

and

The game is the following: Given a sequence of consecutive integers, draw a graph where the nodes are the integers and there is an edge between each integer if their sum is a square number.

If we take the numbers from 1 to 12, then the following would be the associated graph (note that there are three disconnected pieces of it).

Note that this is a disconnected, undirected graph. Looking at some of the edges.…