Seven graphs that must link

Six points joined in every way cannot be placed in space without some pair of disjoint triangles linking, like two rings of a chain. The proof is a parity count: over the ten ways of splitting the six points into two triangles, the linking numbers always add to an odd number, so at least one of them is not zero. A graph with this property — every placement in space contains two disjoint cycles that link — is called intrinsically linked.

$K_6$ is the smallest complete graph with the property, but not the only graph. The natural question, like Kuratowski’s for drawing on paper, is which graphs are intrinsically linked, and the answer is one of the neatest in the subject: exactly the graphs that contain one of seven particular graphs as a minor. This essay builds the seven, checks the parity on every one of them, and checks that none of them has an edge to spare.

Trading a triangle for a star #

The seven graphs come from $K_6$ by one operation and its reverse. The triangle–star exchange, or $\Delta Y$ move, takes a triangle of three vertices joined in pairs, deletes its three edges, and adds a new vertex joined to all three. The reverse, $Y\Delta$, takes a vertex with exactly three neighbours, none joined to each other, deletes it, and joins the three in a triangle. Both moves keep the number of edges the same.

Starting from $K_6$ and applying every possible exchange to every graph found, keeping only graphs not isomorphic to one already found, the search stops after seven. They are $K_6$ itself; two graphs on seven vertices, one of them $K_{3,3,1}$, three vertices joined to three others with a seventh joined to all six; two on eight, one of them $K_{4,4}$ with a single edge removed; one on nine; and the Petersen graph on ten, every vertex of degree three and no triangle anywhere. This is the Petersen family, named after its best-known member.

The exchange moves between them are drawn as arrows, and they show the family’s shape: a chain from $K_6$ through graphs of seven, eight and nine vertices to the Petersen graph, with $K_{3,3,1}$ and $K_{4,4}$ minus an edge off to the side. Isomorphism was checked exactly, by searching for a matching of vertices that preserves every edge, after a cheap fingerprint of degrees and triangles had ruled most pairs out.

Why the exchange preserves linking #

The exchange is the right operation because it carries intrinsic linking with it. Suppose a graph $G$ with a triangle is intrinsically linked, and $G'$ is obtained by trading that triangle for a star. Take any placement of $G'$ in space. Shrink the new vertex and its three edges toward the centre of the star, and draw straight-ish edges between the three old vertices through that region: the result is a placement of $G$ in which every cycle of $G$ corresponds to a cycle of $G'$ traced through the star, running close to it. Since $G$’s placement links two disjoint cycles, the corresponding cycles in $G'$ link too.

So $\Delta Y$ never destroys intrinsic linking. The reverse move, $Y\Delta$, does not preserve it in general, but within this family it happens to, and all seven are intrinsically linked. The parity argument for $K_6$ goes through for each, as the next figure checks, and Horst Sachs had shown the Petersen graph and $K_{3,3,1}$ intrinsically linked in 1983, the same year as John Conway and Cameron Gordon’s paper on $K_6$.

The parity on every member #

For each of the seven graphs the relevant count is over pairs of cycles that share no vertex, and the claim is that their linking numbers always add to an odd number.

Every one of the 420 placements gives an odd total. The pairs to check shrink along the chain: ten pairs of triangles in $K_6$, nine pairs in each graph on seven vertices, eight or nine on eight, seven on nine, and six in the Petersen graph, where every disjoint pair is two pentagons. Each exchange changes which cycles exist, and the count drops by one along the chain, but the parity never changes.

The linking numbers themselves are computed without drawing anything. For two closed polygons in space, Gauss’s double integral for the linking number has a closed form edge by edge — each pair of straight edges contributes a solid angle — and summing those gives the linking number exactly, up to rounding, which is checked to be within a millionth of a whole number before it is rounded. The figure uses the result from every pair of disjoint cycles in every placement.

Why a crossing change cannot spoil the parity #

The parity is proved the way it is for $K_6$. Any placement can be deformed into any other by moving the edges through space, and the only moments at which a linking number changes are when one edge passes through another. Such a crossing change between two edges $e$ and $f$ that share no vertex changes the linking number of a pair of disjoint cycles by one exactly when one cycle contains $e$ and the other contains $f$; every other pair is untouched. So the total over all pairs changes by the number of disjoint cycle pairs that separate $e$ from $f$, each contributing plus or minus one.

For the parity to survive, that number must be even for every choice of two vertex-disjoint edges, and in each member of the family it is. In $K_6$, two disjoint edges lie in opposite triangles of exactly two of the ten splits. Across the whole family the count, computed for every two disjoint edges of every member, is always two or four — never odd. That is the whole reason the argument works: the linking number counts crossings, and the family’s combinatorics make every crossing change count twice or not at all. Then one placement with an odd total — found in the figure above for every member — fixes the parity for all placements.

Counting the cycle pairs #

The numbers in the table’s second column fall by one along the chain of exchanges, and the reason is visible in the exchange itself. When a triangle becomes a star, every cycle that used one or two of the triangle’s edges is rerouted through the new vertex, and it stays a cycle; so every pair of disjoint cycles survives, rerouted, except the pairs in which the triangle itself was one of the two cycles. The triangle is gone, and its partners go with it.

In $K_6$ each triangle has exactly one disjoint partner, the triangle on the other three vertices, so the first exchange loses exactly one pair: ten becomes nine. Along the chain the same happens at each step, until the Petersen graph, with no triangle left to exchange, keeps its six pairs of pentagons. The two side members, $K_{3,3,1}$ and $K_{4,4}$ minus an edge, keep nine pairs each, and their cycles are longer: $K_{4,4}$ minus an edge has no triangles at all, so its disjoint pairs are made of four-cycles.

Two pentagons, hooked #

The Petersen graph is the member that looks least likely to link. It has no triangles; every vertex has only three edges; its shortest cycles have five edges each.

Its twelve five-edge cycles come in six complementary pairs — each pentagon’s five vertices leave five others that also form a pentagon — and those six pairs are all the disjoint cycle pairs the graph has. In the placement drawn, one pair links and five do not, a total of $-1$. Move the points however one likes, and the six linking numbers keep adding to something odd: at least one pair of pentagons is always hooked through the other.

The Petersen graph appears in the proof that it contains $K_5$ after contraction, as the largest graph of degree three in which every vertex is two steps from every other, and in several questions where it is the smallest counterexample, and its role here is similar. It is the sparsest graph that cannot be placed in space unlinked: fifteen edges, like every member of the family, spread over ten vertices.

No edge to spare #

A graph containing a family member is intrinsically linked, because any placement of the larger graph contains a placement of the member, or of a graph from which the member arises by contracting edges, and the linking survives. The theorem says more: the seven are minor-minimal. Deleting any edge, or contracting any, gives a graph that can be placed without linking.

The deletion half can be seen directly. With any single edge removed, every one of the seven graphs has placements in which no two disjoint cycles link — between a tenth and a fifth of random placements, for the least favourable edge. Random points are a crude way to find them, and they find them easily. The full graphs never have such a placement, because the parity forbids it; the graphs less an edge have lost a cycle pair the parity needed, and nothing forces the rest.

As little linking as possible #

The fewest-linked column of the table is 1 for every member: among sixty random placements of each graph there was always one in which exactly one pair of disjoint cycles linked, necessarily with an odd linking number. The parity allows no less, and the random placements reach that minimum easily. So the theorem is sharp in a second sense. Not only can no placement avoid linking; the best placement links exactly once, and the family’s graphs can be placed so that a single pair of cycles is hooked and everything else hangs free.

The average column says the opposite extreme is not typical either. A random placement links about two pairs on average, a little more in the larger graphs, which have longer cycles that wander further through the cube. None of that is forced. What is forced is only the parity — an odd number of hooks, counted with sign — and the rest is the geometry of wherever the points happened to fall.

Linked in pairs, not in threes #

The property the family forces is the simplest kind of linking: two closed curves, one passing through the other. Space allows subtler kinds. Three rings can be linked together although no two of them are, and linking numbers, which see only pairs, cannot detect that. Graphs forced to contain a link of three cycles that cannot be pulled apart exist too, and they are larger: Erica Flapan, Ramin Naimi and James Pommersheim showed in 2001 that every placement of the complete graph on ten vertices contains one. The Petersen family answers only the pairwise question, and that question is exactly the one a single integer invariant can settle.

The theorem that the seven are all #

In 1995 Neil Robertson, Paul Seymour and Robin Thomas proved the converse: a graph is intrinsically linked if and only if it contains a member of the Petersen family as a minor. A graph with none of the seven as a minor has a placement in space with no two disjoint cycles linked — and in fact a stronger kind of placement, which they called flat, in which every cycle bounds a disc that the rest of the graph does not cross.

The result is the three-dimensional counterpart of Kuratowski’s theorem, which says a graph can be drawn in the plane without crossings exactly when it contains neither $K_5$ nor $K_{3,3}$ as a minor. The resemblance is closer than it looks. Both lists are finite; both were conjectured long before they were proved; and the proof of the spatial version used the machinery of the Graph Minors project, in which Robertson and Seymour proved that every property closed under taking minors is characterised by a finite list of forbidden minors. That general theorem says a finite list exists; finding it is a separate problem, and for linking the answer is seven.

Linking and knotting #

The contrast with knots is sharp. Seven points joined in every way always contain a knotted cycle, by a similar parity argument with the Arf invariant in place of the linking number. But the list of minor-minimal intrinsically knotted graphs is not known. It is finite, by the Graph Minors theorem, and it is long: hundreds of members have been found, many of them by triangle–star exchanges from $K_7$, whose family has twenty members of which only fourteen are intrinsically knotted — unlike the Petersen family, where all seven are linked. Some graphs reached from $K_7$ by $Y\Delta$ moves can be placed with every cycle unknotted.

Linking is simpler for a reason the parity count makes visible. The linking number is an invariant of a pair of curves, easy to compute and additive; a crossing change between two edges changes the linking numbers of exactly the cycle pairs that use both edges, and in every family member that number is even. For knotting the invariant is subtler, and the combinatorics of which cycles a crossing change affects is messier. The Petersen family is what a clean invariant buys.

What the placements cannot show #

Every placement here is straight-line, from random points in a cube, and the linking numbers are computed exactly for those placements. The parity theorem is about every placement, including curved and tangled ones, and sixty placements per graph confirm it rather than prove it; the proof is the crossing-change argument.

The minor-minimality figure checks only edge deletion, and only by finding unlinked placements among random ones. The contraction half, and the theorem that nothing outside the family is needed, are not reached by any finite sampling: the Robertson–Seymour–Thomas proof is long and structural, and no computation replaces it. And the family itself was generated by a search that could in principle have missed a member if two non-isomorphic graphs had been judged isomorphic; the exact isomorphism test, run whenever fingerprints agreed, rules that out.

Still open: where linking gets stronger #

The Petersen family settles which graphs must link. It does not settle how badly. Larger complete graphs are forced to contain more complicated linking: $K_{10}$ must contain a pair of cycles with linking number at least 2 in absolute value, and larger graphs are forced to contain links of three components that cannot be separated, and chains of links. For each such stronger property the minor-minimal graphs are finite in number and almost entirely unknown.

The knotted side is open at its root: the complete list of minor-minimal intrinsically knotted graphs is unknown, and no characterisation analogous to the Petersen family is in sight. What the linking case shows is that such a list can be short, generated by a single local move from one graph, and verified by one parity — and that is not what the knotting case looks like.

What the seven have in common #

Seven graphs, fifteen edges each, connected by an exchange of triangles for stars, and every placement of every one of them hooks two disjoint cycles together. The parity that forces the link in $K_6$ travels unchanged along the exchanges to the Petersen graph, where it hooks two pentagons; and removing any single edge from any of the seven lets every link fall apart. Kuratowski’s two graphs tell a graph whether it can lie flat on a page. These seven tell it whether it can sit in space with nothing caught.

Both lists are forced by the simplest invariant available — for the page, the parity of crossings; for space, the parity of linking — and both are complete because a structural theorem guarantees that nothing else is needed. The invariant finds the obstructions; the theorem proves there are no others.