Six points in space and a pair that must link

Five points in the plane, every pair joined by a curve: two of the curves must cross. That is the non-planarity of $K_5$, the complete graph on five vertices, and it is one of the two obstructions to drawing a graph flat.

Move up a dimension and crossing is no longer a problem. In space every graph can be drawn with no two edges meeting — put the vertices on a curve that twists enough, and every chord between them misses every other. What space introduces instead is linking. A cycle in a graph drawn in space is a closed curve, and two disjoint cycles are two closed curves, which can be linked like the rings of a chain.

In 1983 John Conway and Cameron Gordon, and independently Horst Sachs, proved that linking in space is as unavoidable for $K_6$ as crossing in the plane is for $K_5$: however the complete graph on six vertices is placed in space, some two of its disjoint triangles are linked. The proof is a parity argument, and every piece of it can be checked.

Ten ways to split six points #

Six vertices can be divided into two groups of three in $\binom{6}{3}/2 = 10$ ways. Each group spans a triangle — three edges of $K_6$ — and the two triangles are disjoint, so they have a linking number, computed by the crossing count of any projection.

In the drawing only one of the ten pairs is linked. The orange triangle through vertices 1, 2 and 6 and the blue triangle through 3, 4 and 5 pass through one another like two links of a chain: the orange triangle’s edges cross the blue triangle’s in projection with signs that add to $-2$, and halving gives linking number $-1$. The other nine pairs are unlinked — for each of them the signed crossings cancel, or there are none.

Every linking number in the table was computed twice, by methods that share nothing. The crossing count looks at one projection of the two triangles and adds signs. Gauss’s integral looks at the triangles in space with no projection, and for straight segments it has a closed form: each pair of segments contributes the solid angle one subtends as seen along the other, divided by $4\pi$. The two agree to machine precision in every case, which is both a check on the drawing and a small instance of the theorem that the linking number does not depend on the projection.

Two thousand placements, never an even count #

Before the proof, the experiment.

Two features stand out. The number of linked pairs is always odd. And it is only ever one or three — never five, never seven, though ten pairs are available. The first feature is Conway and Gordon’s theorem. The second is a special property of straight segments: for embeddings built from straight lines it has since been proved that the number of linked triangle pairs is always exactly one or three. With curved edges there is no such ceiling on the linking — edges can be wound round each other as often as desired — and only the parity survives.

The proportions are worth a moment. Three placements in four have the minimum of one linked pair. That is not forced by anything; it is a fact about what six random points in a cube tend to look like, with most of them spread out so that only one pair of triangles is threaded through the other. The placements with three linked pairs tend to be the compact ones, where the points crowd together and several triangles pass through each other at once. The census counts the linking of every one of the 20,000 triangle pairs in these placements, each confirmed by the exact Gauss integral, and never once finds the ten numbers adding to something even.

Moving a vertex, and a count that jumps by two #

Take the placement drawn above and slide vertex 6 along a straight line through the middle of the configuration to the far side. At every position, recount the linked pairs.

The count changes only at the moments when an edge through vertex 6 passes through another edge — when two segments of the graph momentarily meet in space. Between those moments nothing can change, because the triangles move continuously without touching, and linking numbers are invariant under exactly that kind of motion. At each such moment the count jumps by two.

The reason is a small piece of counting, and it is the whole proof. Suppose edge $e = ab$ passes through edge $f = cd$, where the four vertices are different. That is a crossing change: in projection, one strand that was over becomes under. Which triangle pairs notice? Only those in which $e$ lies in one triangle and $f$ in the other. The remaining two vertices, call them $u$ and $v$, must be shared out one to each triangle, so there are exactly two such pairs: $\{a, b, u\}$ with $\{c, d, v\}$, and $\{a, b, v\}$ with $\{c, d, u\}$. Each of those linking numbers changes by one. So the sum of the ten linking numbers changes by $+2$, $0$ or $-2$, and its parity is unchanged.

If the two edges passing through each other share a vertex, no triangle pair contains both of them in different triangles, and nothing changes at all.

The moving-vertex figure is this argument caught in the act. Three times on its path an edge through vertex 6 passes through another edge, and three times the count of linked pairs jumps by exactly two — from one to three, when two pairs that were unlinked become linked; back to one, when a linked pair and another come apart together; and up again. What never happens, at any of the 241 positions, is a single pair changing on its own.

The parity is always odd #

Any two placements of $K_6$ in space can be turned into one another by a continuous motion in which edges are allowed to pass through each other finitely many times. By the counting above, no such passage changes the parity of the sum of the ten linking numbers. So that parity is the same for every placement, and it can be read off from any single one.

The placement drawn at the top has sum $-1$. Therefore every placement has an odd sum, and an odd sum of ten integers has at least one odd term. Some pair of disjoint triangles has odd linking number, so it is linked — in every placement of $K_6$ in space, with curved edges or straight, tangled or tidy.

The argument has the same shape as the proof that $K_5$ cannot be drawn flat in one of its standard forms: in the plane, count the crossings between pairs of disjoint edges, observe that moving the drawing changes that count only by even amounts, and exhibit one drawing where it is odd. Space replaces “crossings of disjoint edges” by “linking of disjoint cycles”, and the same parity bookkeeping does the rest.

The same bookkeeping in the plane #

The parity argument has an older twin, one dimension down, and seeing them side by side shows what is really being proved.

Draw $K_5$ in the plane, edges as curves allowed to cross. For every pair of edges with no common vertex, count how many times they cross, and add these counts over all such pairs. Now move the drawing. The count changes only when an edge is swept across a vertex, and when edge $e$ passes over vertex $v$ it changes its crossing number with every edge at $v$ that is disjoint from $e$ — and in $K_5$ there are exactly two such edges, since $v$ has four edges and two of them go to the ends of $e$. So the total changes by an even amount, and its parity is the same for every drawing. The convex drawing, a pentagon with its five diagonals forming a star, has five crossings, every one between disjoint edges — an odd number. So every drawing has an odd number of such crossings, at least one, and $K_5$ cannot be drawn without a crossing.

The two arguments are the same argument. In the plane the objects that must meet are pairs of disjoint edges and the invariant is their crossing parity; in space the objects are pairs of disjoint cycles and the invariant is their linking parity. In both, a local move changes exactly two of the counted quantities, and one example fixes the parity for all. The general theory behind both is due to Egbert van Kampen, who in the 1930s defined an obstruction of exactly this kind for embedding any complex of dimension $n$ in space of dimension $2n$: the plane is $n = 1$ with $K_5$, space for linking is its cousin one step up.

Five points are not enough #

The complete graph on five vertices has no two disjoint cycles at all — a cycle needs three vertices, and two disjoint ones need six — so nothing about $K_5$ can be linked, and it can be placed in space with no linked cycles trivially. $K_6$ is the smallest complete graph where the question even makes sense, and for it the answer is already forced.

There is a second graph with the same property whose smallness is less obvious. $K_{3,3,1}$ — three vertices joined to three others, and a seventh joined to all six — also cannot be placed in space without linking. So can the Petersen graph, with ten vertices of degree three. Together with four more graphs, obtained from these by trading a triangle for a three-pointed star or back, they form the Petersen family of seven graphs. In 1995 Neil Robertson, Paul Seymour and Robin Thomas proved that a graph can be placed in space with no linked cycles exactly when it contains none of the seven as a minor — the spatial counterpart of Kuratowski’s theorem that a graph can be drawn in the plane exactly when it contains neither $K_5$ nor $K_{3,3}$.

One more vertex, and a knot #

Conway and Gordon’s paper had a second theorem. Every placement of $K_7$ in space contains a knotted cycle — a closed path through all seven vertices that is not an unknotted loop.

The proof follows the same plan with a different invariant. Instead of the linking number of a pair of cycles, it uses a mod-2 invariant of a single cycle — the Arf invariant, which is 0 for the unknot and 1 for the trefoil — summed over all Hamiltonian cycles of $K_7$. A crossing change between two disjoint edges changes the Arf invariant of a fixed number of those cycles, and that number is even, so the parity of the sum is again independent of the placement; one placement with exactly one knotted Hamiltonian cycle, a trefoil, shows the sum is odd. The pattern is general: pick an invariant, find a sum of it over a family of subgraphs whose parity crossing changes cannot alter, and exhibit one placement where the sum is odd. The difficulty is finding the invariant and the family.

For linking the invariant was the linking number and the family the pairs of disjoint triangles; a crossing change touched two members of the family. For knotting the invariant has to see a single closed curve, and the linking number cannot, so the Arf invariant — computable from the Alexander polynomial at $-1$, modulo 8 — takes its place. Then a crossing change between two disjoint edges of $K_7$ alters the Arf invariant only of Hamiltonian cycles passing through both edges in a particular pattern, and Conway and Gordon counted those cycles and found an even number. The two theorems are one method applied twice, and the method is the reason the paper is short.

What a sum of integers hides #

The theorem says a sum of ten linking numbers is odd. It does not say which pair is linked, and the census shows that the linked pairs differ from placement to placement. That is the same trade the ribbon made between twist and writhe: a quantity that cannot change is distributed among parts that can, and the constraint lives only in the sum. Here the parts are the ten triangle pairs and the constant is the parity; move a vertex and the linking passes from one pair to another two at a time.

It is also a reminder that pairwise linking is not the only kind. Three rings can be inseparable while no two of them are linked, and a graph placed in space can have that more delicate kind of entanglement too. Conway and Gordon’s argument sees only linking numbers, so it detects only the pairwise kind — which is enough to prove that entanglement is unavoidable, and says nothing about how elaborate it can be made. A placement of $K_6$ whose only entanglement were Borromean — three triangles mutually inseparable with every pair unlinked — is impossible for the simple reason that $K_6$ has room for only two disjoint triangles. For larger graphs the subtler kinds of entanglement become possible, and whether they too can be forced is a separate question with separate answers.

What the figures establish, and what they only illustrate #

The census is not the proof. Two thousand random straight-line placements with odd counts are evidence, and the census’s claim that the count is always one or three is a statement about straight segments that the figure checks without proving. The theorem for all placements, curved edges included, is the parity argument, which the moving-vertex figure illustrates on one path.

The moving vertex passes through edges, not around them. At the positions where the count jumps, an edge through vertex 6 meets another edge in space — the placement at that instant is not an embedding. The figure samples 241 positions and never lands exactly on such an instant; what it shows is the count on either side.

Only straight edges are drawn. Every figure uses straight segments because their linking numbers can be computed exactly. The theorem allows arbitrary curved edges, and for those far more linking is possible than any figure here shows.

The drawings are squeezed. Each placement is projected and then stretched horizontally and vertically by different amounts to fill the panel. A linear change of the page moves no crossing and swaps no over for under, so every count read from the drawing is unchanged, but angles and proportions in the pictures are not those of the points in space.

Still open: how much entanglement is forced #

The existence of one linked pair is settled; how much linking a graph forces is not. For large complete graphs every placement contains many linked pairs and cycles linked in complicated ways — any placement of a large enough complete graph contains, for instance, a pair of cycles with linking number at least any given size — and the minimum amount of linking that $K_n$ forces, as a function of $n$, is known only within wide bounds, and the gap between the constructions and the lower bounds is large. Even for straight-line placements, where the census above showed $K_6$ confined to one or three linked pairs, the corresponding ranges for $K_7$, $K_8$ and beyond are determined only partly, by a mixture of proof and computer search over the finitely many combinatorial types of point configuration.

The knotted side is less understood still. Which graphs are intrinsically knotted — must contain a knotted cycle in every placement — has no characterisation analogous to the Petersen family. Many minimal intrinsically knotted graphs are known, the list is known to be finite by Robertson and Seymour’s general theory of graph minors, and nobody knows what the list is.

An obstruction that lives in the sum #

Six points in space look like the simplest possible configuration, and there is no clever way to place them that avoids a linked pair. The proof never finds the linked pair, and could not in general, since which pair it is depends on the placement: it shows that the ten linking numbers have an odd sum, a fact that moving the points cannot change, and lets arithmetic do the rest. That a question about tangled triangles is settled by the parity of a count, and that no drawing of the configuration is needed to prove it, — the same kind of argument that forces two edges of $K_5$ to cross — is the connection between the plane and space that the theorem makes precise.

And it is a theorem that can be tested with a handful of beads and string. Six beads, fifteen strings, any arrangement at all: some two of the triangles will hang together like links of a chain. The census above is two thousand arrangements of that experiment done by exact arithmetic, and the proof is the reason none of them could have come out differently.