Points and lines: let the maths festivities begin!

It is hard to know when maths will take hold of you. It can all begin very simply, perhaps during a long telephone call to a government office that is difficult to reach. Without thinking, you pick up a pen as a Vivaldi tune plays over and over, and you begin to doodle. You might, for example, end up with the drawing opposite.

You have placed eight points and drawn eight of the possible segments joining them. The shape of a "9" seems unremarkable, but one feature catches your eye: all the segments you have drawn are the same length! Once you have hung up, you eagerly complete the drawing by adding two more segments of the same length, one of them inside the loop of the "9". You then find that no others can be added without introducing new points.

A natural mathematical question arises: given a fixed number n of points, what is the maximum number of equal-length segments that can be drawn between them, if the n points may be placed wherever—and however cleverly—you like?

For n = 3, the problem is easy: an equilateral triangle gives a configuration in which every possible segment has the same length.

For n = 4, a square gives four equal-length segments—its sides—but it soon becomes clear that we can do better and obtain five by joining two equilateral triangles along one of their sides. A geometric argument then shows that a configuration of four points cannot have six equal-length segments—and proving this is a small challenge left to our readers' ingenuity.

Experiments with small numbers of points.

For n = 5, seven equal-length segments can be obtained by adding an equilateral triangle along one of the outer sides. But could a cleverer arrangement do better?

As you try drawing configurations with slightly larger numbers of points, you manage to work out a few optimal values for small n. You begin to wonder what happens when n becomes truly large. In other words, how quickly does the maximum number of equal-length segments grow as the number of points varies? In doing so, and without realizing it, you rediscover a conjecture by the illustrious Hungarian mathematician Paul Erdős concerning the asymptotic estimate of this quantity!

In a very short paper published in 1946, Erdős announced that it "seemed likely" that the number of segments was asymptotically smaller than n^a for every a > 1. As was his custom, he even offered a reward of five hundred dollars to anyone who could prove or disprove the conjecture! A sign of the result's importance to mathematicians, this was one of the largest rewards he ever offered.

This claim, born of Erdős's intuition, remains an open question today. The best result available dates from... 1984: the maximum number of segments is asymptotically bounded above by n^4/3. This beautiful result is due to the mathematicians Joel Spencer, Endre Szemerédi (who also won the 2012 Abel Prize) and William Trotter. The bound was improved by Lazlo Székely in 1997, but we should bear in mind that many possible values for the exponent a remain between 1 and 4/3. Erdős's conjecture still stands...

As so often when studying questions about graphs, we can turn to the Petersen graph. It is easy to remember, looking as though it emerged from some satanic ritual. More seriously, it proves to be a formidable counterexample to many mathematical intuitions.

The Petersen graph and its satanic appearance.

For our purposes, however, it looks deeply disappointing: the segments are not all the same length, although those in the central pentagon are. Yet by rotating the outer points judiciously and "stretching" the figure a little, we can make every segment the same length! We alter the diagram but retain the segments joining the points: they remain "attached" and "connected" as the points move. This gives another representation of the Petersen graph, now possessing the desired property.

Another representation of the Petersen graph. This time, all the segments have the same length.

In technical terms, a graph that can be drawn with all its segments the same length is called a unit-distance graph. Here is a second, seemingly innocuous mathematical question: are all graphs unit-distance graphs? In other words, for every drawing of a graph, can the points be moved so that all the segments drawn have the same length? The answer is no, as you already know if you took up the small challenge at the beginning. With four points, at most five equal-length segments can be drawn. Consequently, if we take four points and join them with six segments—that is, draw every possible segment—we obtain a graph that will always have two segments of different lengths, however its points are moved.

Let's change the question: how can unit-distance graphs be recognized? The problem is rather difficult—very difficult, in fact. To see why, consider this highly unusual graph, known as the Heawood graph.

The Heawood graph, with its fourteen points and twenty-one segments.

In this diagram, the segments are not all the same length. That is easy to check. But it would take a very clever person to determine whether the Heawood graph has a representation in which all the segments are the same length! Finding a suitable representation is difficult, whereas checking whether a particular drawing has the property is easy. In 2013, the German mathematician Marcus Schaefer established that this problem was NP-complete, meaning, roughly speaking, that it belongs to a class of equivalent problems regarded as very difficult to solve, but whose solutions can be checked easily.

That said, it can be proved that the Heawood graph really is a unit-distance graph.

The example of four points in the plane also helps explain how to identify graphs that are not unit-distance graphs. It is impossible to draw six equal-length segments. That is not entirely true—or rather, it is true in the plane. If we draw the figure in three dimensions instead, it is easy to construct a regular tetrahedron whose edges are all the same length!

For an arbitrary graph, three dimensions are not always enough, so we introduce the notion of the minimum dimension of a space in which the graph has a representation whose segments are all the same length (see box). We began with a drawing doodled while waiting on the telephone, and now we have been propelled into the fourth dimension or beyond! You really never know when mathematics will take hold of you...