The colours a circle forces

Choose two things from five — there are ten ways — and draw a point for each choice. Join two points when the choices share nothing: $\{1,2\}$ is joined to $\{3,4\}$, $\{3,5\}$ and $\{4,5\}$, and to nothing else. The drawing that results is the Petersen graph, the most frequently drawn counterexample in graph theory, and the question here is how many colours it needs so that joined points always get different colours.

Three colours are enough, and the rule in the figure shows why at a glance. Two orange pairs both contain $1$, so they are not disjoint and not joined; two blue pairs both contain $2$; two green pairs lie inside a set of three, and any two pairs from three things share one. Two colours are not enough, because the outer ring of the drawing is a cycle of five, and a cycle of odd length cannot alternate between two colours.

That is the whole answer for this graph, and it is misleading in its ease. The same question for larger graphs of the same kind has an answer that no argument of this sort can reach.

Kneser’s question #

Martin Kneser asked the general version in 1955. Take all $k$-element subsets of $\{1, \ldots, n\}$, and join two when they are disjoint. The result is the Kneser graph $K(n, k)$; the Petersen graph is $K(5,2)$. How many colours does it need?

The colouring in the figure generalises directly. Give a set colour $i$ if its smallest element is $i$, for $i = 1, \ldots, n - 2k + 1$, and give every remaining set one final colour. The remaining sets lie inside the last $2k - 1$ elements, and two $k$-sets inside $2k - 1$ elements must share one. So

$$\chi(K(n,k)) \le n - 2k + 2.$$

Kneser conjectured that this is exactly right — that no colouring uses fewer. For the Petersen graph that is the odd cycle. For $K(6, 2)$ it says four colours, and the search in the figure confirms it, but the confirmation is by trying every three-colouring, not by a reason.

Every counting bound falls short #

The usual ways to prove that a graph needs many colours are counting arguments, and it is instructive to watch each fail.

The first is a clique: a set of vertices every two of which are joined needs a colour each. In a Kneser graph a clique is a family of pairwise disjoint $k$-sets, and at most $\lfloor n/k \rfloor$ of those fit in $n$ elements. For $K(7, 3)$ that is two, and the conjecture says three.

The second is the fractional bound. A colour class is a family of $k$-sets with no two disjoint — an intersecting family — and the largest family that always meets has $\binom{n-1}{k-1}$ members, the sets through one fixed element. So at least $\binom{n}{k} / \binom{n-1}{k-1} = n/k$ colours are needed, and this is the best any argument based on the size of colour classes can do: letting each vertex be split among several colours, $n/k$ is exactly enough.

The table shows the gap growing. For $K(9, 4)$ the clique has two sets, the fractional bound is $2.25$, and three colours are needed. For $K(8, 2)$ the fractional bound is four and six colours are needed. Neither counting bound gets close, and neither can: they measure how large a colour class may be, and the difficulty is not there.

Nothing local explains it #

A graph can need many colours because it contains a dense piece. The Kneser graphs of one family have no dense piece at all, and still need three.

In $K(11, 5)$ there are $462$ vertices, each with six neighbours, and no odd cycle shorter than eleven. Any part of the graph smaller than an eleven-cycle can be coloured with two colours; locally the graph looks exactly like one that two colours would suit. A two-colouring fails only because of how those local pieces join up far away, and a counting argument, which adds up local contributions, has nothing to find.

That is the sign that the obstruction is topological. Something about the way the whole graph fits together forbids two colours, as the winding of a boundary that labels itself forbids avoiding opposite labels, without any single place being responsible.

Five points on a circle #

László Lovász proved Kneser’s conjecture in 1978 using the Borsuk–Ulam theorem, and Imre Bárány found a shorter proof the same year. At the Petersen graph, Bárány’s proof lives on a circle, and every step can be drawn.

Put the five elements at the corners of a regular pentagon on a circle. Every open half-circle then contains at least two of them. Now suppose the pairs had been coloured with two colours. For each direction $x$ round the circle, look at the open half-circle centred on $x$; it contains at least two points, hence at least one pair. Mark $x$ with colour $c$ if some pair of colour $c$ lies inside that half-circle.

Every direction gets at least one mark, and the set of directions marked with a given colour is open — a pair strictly inside a half-circle stays inside when the half-circle turns slightly. So the circle is covered by two open sets, one per colour. If neither set contained a pair of opposite directions, each would be disjoint from its own reflection, which forces the second to be exactly the reflection of the first; then the two would be disjoint open sets covering the circle, which is impossible because a circle does not fall into two separated pieces. So some direction $x$ and its opposite carry the same colour $c$.

The half-circles centred at $x$ and at its opposite do not overlap. The pair of colour $c$ inside one and the pair of colour $c$ inside the other are therefore disjoint — two joined vertices with the same colour. The colouring was not proper after all. Any two-colouring of the Petersen graph produces a direction that cannot be told apart from its opposite, and that is the edge it gets wrong.

Why the points must be spread #

The proof used the positions of the five points exactly once: to guarantee that every half-circle holds a pair.

With the points bunched, a large arc of directions gets no mark, the marked sets no longer cover the circle, and the argument about opposite directions has nothing to act on. The graph has not changed — its vertices are still the ten pairs — but this placement of the elements cannot see its structure. The spreading condition has a name: Gale’s lemma, from David Gale in 1956, says that $2k + d$ points can be placed on the $d$-dimensional sphere so that every open hemisphere contains at least $k$ of them.

On a circle the spreading is easy — a regular polygon does it — and in higher dimensions it is not much harder. Gale’s construction puts the points on a curve that winds round the sphere, alternating from side to side, so that any hemisphere, however it is tilted, cuts off a long enough run of them. What matters is only that no hemisphere can be nearly empty; the particular positions are otherwise free, and the colouring is never consulted when choosing them.

For the general Kneser graph with $n = 2k + d$, the argument runs on the sphere of dimension $d = n - 2k$. A colouring with $d + 1$ colours marks the sphere with $d + 1$ open sets, one per colour; they cover it by Gale’s lemma; and the theorem that $d + 1$ open sets covering a $d$-sphere must include one containing an opposite pair — the covering form of Borsuk–Ulam, the three regions of the agreeing pair of points — produces two disjoint $k$-sets of one colour. So $n - 2k + 1$ colours never suffice, and with the smallest-element colouring the answer is exactly $n - 2k + 2$.

On a circle the covering theorem was just the fact that a circle is connected. On the sphere of dimension two it is the theorem about three regions; beyond that it is Borsuk–Ulam in full, and that is where the argument needs the topology that Tucker’s lemma supplies by counting.

Lovász’s route, and the shortest one #

Bárány’s proof is the easiest to draw, but it was not the first. Lovász attached to any graph a space built from its neighbourhoods — the neighbourhood complex, whose simplices are the sets of vertices with a common neighbour — and proved that if this space is highly connected, in the sense that spheres of every dimension up to some $t$ can be filled in inside it, then the graph needs at least $t + 3$ colours. For the Kneser graph the space is connected up to dimension $n - 2k - 1$, which gives exactly $n - 2k + 2$. The connectivity is where Borsuk–Ulam enters: a colouring with too few colours would give an odd map from a high-dimensional sphere to a lower one, which the theorem forbids.

That general statement, a lower bound on colours from the shape of a space, turned a single conjecture into a method. Noga Alon, Peter Frankl and Lovász used a version of it in 1986 to settle Erdős’s question about colouring the $r$-element analogue, where colour classes must avoid $r$ pairwise disjoint sets rather than two.

The shortest proof came much later, from Joshua Greene in 2002, written while he was an undergraduate. Place $n$ points on a sphere of dimension $d = n - 2k + 1$ so that no great sphere contains more than $d$ of them, and for each colour mark the directions whose open hemisphere contains a set of that colour; add one more set for the directions whose hemisphere contains no $k$-set at all. The covering form of Borsuk–Ulam, applied to these $n - 2k + 2$ sets, forces an opposite pair into one of them. If it is a colour set, the two opposite hemispheres hold disjoint sets of one colour; if it is the extra set, both hemispheres hold fewer than $k$ points, which leaves at least $d + 1$ of the $n$ points on the great sphere between them — more than the placement allows. The proof fits on half a page, and Gale’s lemma is not needed.

Large gaps with no short cycles #

The odd graphs are an explicit instance of something whose existence was first shown by chance. The colouring nobody has ever seen records Erdős’s theorem of 1959: there are graphs with no short cycles and as many required colours as wished. Its proof builds a random graph, deletes a few edges, and exhibits nothing.

Kneser graphs make part of that concrete. The odd graphs have no short odd cycles and need three colours. More generally, $K(2k + t, k)$ needs $t + 2$ colours, and when $k$ is much larger than $t$ its shortest odd cycle has length about $2k/t$ — so taking $t$ large and $k$ larger still gives graphs with no short odd cycle that need as many colours as wished. Each of these is a specific graph, with a specific reason for its colour count. Colouring is supposed to be a local matter, and these graphs are the cleanest evidence that it is not — the reason lies in the global shape, and the shape is a sphere.

The same thought explains why counting colourings is of no help here. The chromatic polynomial of a Kneser graph does answer the question, since its first positive value at a whole number is the colour count, but computing it means knowing every colouring. The topological argument answers the question without counting a single colouring, which is why it could succeed where counting stalled.

Stable sets that need every colour #

The proof suggests which vertices matter. Only $k$-sets lying inside half-circles were ever used, and on a regular polygon those are the sets spread round it rather than bunched. Alexander Schrijver made that precise in 1978.

Call a $k$-set stable if no two of its elements are neighbours round the circle $1, 2, \ldots, n$. The stable sets form a much smaller graph — $9$ vertices instead of $126$ for $K(9,4)$ — and Schrijver proved that they still need all $n - 2k + 2$ colours. Moreover, they are critical: remove any one stable vertex and one colour fewer suffices. So the stable sets are exactly the part of the Kneser graph that makes it hard, and nothing smaller is.

For the Petersen graph the stable sets are the inner pentagram, a single five-cycle. The count of stable sets has a closed form, $\tfrac{n}{n-k}\binom{n-k}{k}$ — the number of ways to choose $k$ points round a circle of $n$ with no two adjacent — which is far smaller than $\binom{n}{k}$ once $k$ is close to $n/2$, and that is how nine vertices can carry the whole difficulty of a graph with a hundred and twenty-six. The whole difficulty of colouring the Petersen graph is one odd cycle, which is why it looked easy. For $K(9,4)$ the nine stable sets form a nine-cycle, and the reason that cycle needs three colours is again its odd length. For $K(7,2)$, the fourteen stable pairs need five colours, and no cycle explains that.

What the pictures cannot establish #

Kneser’s theorem beyond the small cases. The searches confirm $n - 2k + 2$ for eight graphs, the largest with $126$ vertices. The theorem for all $n$ and $k$ is Lovász’s, and it rests on Borsuk–Ulam in every dimension; no search approaches it, and for twenty-three years between the question and the proof nobody had found a reason.

The covering theorem in higher dimensions. The Petersen graph needs only the circle, where the covering theorem is the connectedness of a circle. For $K(6,2)$ the sphere is two-dimensional, and the fact that three open sets covering it include one with an opposite pair is a genuine theorem that the circle picture does not contain.

Why the stable sets are critical. The table checks criticality vertex by vertex for six graphs. Schrijver’s proof is a sharpening of the topological argument, and it is the argument, not the check, that covers every size.

Still open: several colours on every vertex #

Kneser graphs are the natural test for a variant of colouring. Give every vertex $m$ colours instead of one, with joined vertices sharing none, and ask for the fewest colours in total. With $m = k$ there is a perfect answer: give each $k$-set its own $k$ elements as colours, and disjoint sets share nothing, so $n$ colours suffice — and fewer cannot.

Saul Stahl conjectured in 1976 a formula for every $m$: writing $m = qk - r$ with $0 \le r < k$, exactly $qn - 2r$ colours are needed. It gives Lovász’s $n - 2k + 2$ at $m = 1$ and the perfect $n$ at $m = k$. Stahl’s conjecture is proved for several families of cases and open in general, and the topological methods that settle $m = 1$ have not been made to reach the rest.

A reason that is not a count #

The Petersen graph needs three colours for a reason anyone can see, an odd cycle. The odd graphs need three colours for no local reason at all, and the Kneser graphs in general need $n - 2k + 2$ for a reason no count can supply. What supplies it is a placement of the elements round a sphere, spread so that every hemisphere holds a set, and the fact that a sphere cannot be covered by too few open sets without one of them catching two opposite points.

At the smallest size the sphere is a circle and the fact is that a circle is connected. That one step up from a circle turns connectedness into Borsuk–Ulam is the same step the halving line, the agreeing pair of points and the shared necklace took — and here it answers a question about colouring graphs that was open for twenty-three years and was never about geometry.