Mathematicians show that graphs of a certain common type must contain a route that visits each point exactly once.
As mathematical abstractions go, graphs are among the simplest. Scatter a bunch of points in a plane. Connect some of them with lines. That’s all a graph is. And yet they are incredibly powerful. They can be used to attack a wide variety of problems, from modeling neurons in the brain to routing delivery trucks on the roads. Within math, they can be used to categorize important algebraic objects called groups, to describe knots, and in myriad other ways.One of the central problems in graph theory is finding routes that visit each point in a graph exactly once before returning to their starting point. These routes are called Hamiltonian cycles, after the 19th-century mathematician William Rowan Hamilton.Many graphs have such cycles. But in others, no matter how hard you try to find a Hamiltonian cycle, you’ll end up stuck: Maybe you’ll get trapped in an isolated bubble of the graph, with no way to visit all the points, or maybe you’ll be forced to retrace your steps.