No triangle, and four colours

A colouring of a graph gives each point a colour so that joined points differ, and the chromatic number is the fewest colours that do it. There is one obvious reason a graph might need many colours: it might contain many points all joined to one another, a clique, every point of which needs its own colour. Four mutually joined points need four colours. The order decides the colours found the opposite bound, that a graph whose points have at most $d$ neighbours never needs more than $d + 1$ colours, and between the two it is natural to guess that a graph’s colour count is governed by its largest clique, perhaps up to a little slack.

The guess is wrong, and badly. There are graphs with no triangle at all — not even three mutually joined points — that need four colours, and five, and any number. They were found in the 1940s and 1950s by Blanche Descartes, Alexander Zykov and Jan Mycielski, and Mycielski’s construction is the cleanest: a single step that takes any graph and returns a larger one needing exactly one more colour, without ever creating a triangle. This essay builds the first few graphs in his sequence, proves their colour counts by exhaustive search, and measures how strange the reason for those counts is.

Eleven vertices, no triangle, four colours #

The smallest graph with no triangle that needs four colours was described by Herbert Grötzsch in 1959. It has eleven points and twenty edges: an outer pentagon, five inner points each joined to two corners of the pentagon, and one point in the middle joined to all five inner points.

That no three points are mutually joined can be checked edge by edge: the two ends of every edge have no common neighbour. That four colours suffice is shown by the colouring drawn. That three do not is the content of the graph, and a search settles it: trying to colour the points one at a time with three colours, always choosing next the point most constrained by its already-coloured neighbours and backing up whenever a point has no colour left, exhausts every possibility after 27 partial colourings and finds none. Vašek Chvátal proved in 1974 that no smaller graph without a triangle needs four colours, so eleven is the threshold.

Twelve thousand ways, and none with three #

The same search can count instead of decide. Grötzsch’s graph has 12,480 proper colourings with four colours. Because three colours are impossible, every one of them uses all four, so they fall into families of 24 that differ only by renaming the colours, and there are exactly 520 genuinely different ways to split its eleven points into four classes with no edge inside a class. Counting the colourings turned such counts into a polynomial in the number of colours, whose value at three is the number of three-colourings; for this graph that value is nought, which is the colour count restated as a root.

The number is worth having because it shows how far from rigid the graph is. A graph that needed four colours because of a clique would have its four-colourings largely forced on the clique and free elsewhere. Grötzsch’s graph has hundreds of essentially different four-colourings and not one three-colouring, and no small part of it explains the difference.

Grötzsch’s own theorem #

Grötzsch’s name is on this graph for a reason that makes it more surprising, not less. His theorem of 1959 says that every graph with no triangle that can be drawn in the plane without crossing edges can be coloured with three colours. The planar graphs as a whole need four — the subject of four colours, and a proof nobody can read — and five colours, and a chain that can be followed showed how much easier five is to prove. Forbidding triangles brings the planar count down to three.

The graph that bears his name shows the theorem needs both of its conditions. It has no triangle and needs four colours, so it cannot be drawn in the plane without crossings; take away planarity and the bound of three fails at eleven points. The difference between the two settings is the whole of this essay: in the plane, the absence of triangles is a strong local condition that forces a small colour count, because planarity limits how the local pieces can be joined; without the plane, local pieces can be joined in Mycielski’s pattern, which builds a global obstruction no local view detects.

A shadow for every corner and one more vertex #

Grötzsch’s graph is the result of applying Mycielski’s step to the five-cycle, and the step works on any graph. For each point $v$, add a shadow joined to all of $v$’s neighbours but not to $v$ itself. Then add one new point joined to every shadow.

No triangle appears. A shadow’s neighbours are the neighbours of its original point, which are not joined to one another if the original graph had no triangle; and the new point’s neighbours are the shadows, which are not joined to one another at all. So a graph with no triangle stays without one.

The colour count goes up by exactly one, by an argument that is worth having in full because it shows where the extra colour comes from. A colouring of the original graph with $k$ colours extends to the new graph with $k + 1$: give each shadow its original’s colour, and give the new point the new colour. Conversely, suppose the new graph could be coloured with $k$ colours. The new point takes one of them; every shadow avoids it, so the shadows use only the other $k - 1$. Now recolour every original point that has the new point’s colour, giving it its own shadow’s colour instead. This is still a proper colouring of the original graph, because the shadow was joined to all the original point’s neighbours and so differs from all of them. But now the original graph is coloured with only $k - 1$ colours, contradicting what it needed. So the new graph needs exactly one more colour than the old.

Starting from a single edge, which needs two colours, the step gives the five-cycle (three), Grötzsch’s graph (four), a graph on 23 points (five), one on 47 (six), and so on, the number of points roughly doubling each time. The same five-cycle is the pentagon that six people at a party found saves five people from a guaranteed trio of friends or strangers: the graph with no triangle whose complement has none either. Here it is the seed of a sequence of graphs with no triangle and ever more colours.

Proving the last colour is needed gets hard fast #

The construction proves the colour counts in general; the search confirms them, graph by graph, and measures the cost of doing so.

The single edge needs 2 partial colourings to show one colour fails, the five-cycle 5, Grötzsch’s graph 27, the 23-point graph 884 and the 47-point graph 447,722. The next graph, with 95 points and needing seven colours, is far out of reach of this search. Mycielski’s graphs are in fact a standard benchmark for colouring programs, used precisely because they are so hard for their size: a search can find a colouring with $k$ colours easily, and proving that $k - 1$ do not suffice requires ruling out an enormous number of partial attempts, because nothing local forces the failure. Each partial colouring looks as though it might extend, and fails only at the end.

A search with no shortcut #

The search used here is not naive. It colours next the point whose coloured neighbours already use the most colours, the rule Daniel Brélaz introduced in 1979, and it never tries a colour beyond the first unused one, which removes the waste of trying every relabelling. Both choices cut the work enormously, and both leave the growth in the previous figure untouched. There is a reason: deciding whether a graph can be coloured with three colours is one of the problems Richard Karp listed in 1972 as NP-complete, as hard as any problem whose solutions can be checked quickly. A fast method for it would give fast methods for satisfiability, scheduling and thousands of other problems, and no such method is known.

Hardness in general does not mean hardness for every graph, and most graphs met in practice colour easily. What makes Mycielski’s graphs a benchmark is that they are hard in exactly the way the theory predicts — the failure of $k - 1$ colours is invisible until a partial colouring is nearly complete, so the search must carry many partial colourings almost to the end before discarding them. The same three-colouring question, rephrased as a list of clauses that each forbid two joined points from sharing a colour, is the kind of problem a walk that beats trying everything attacked with a randomised walk; for triangle-free graphs built to need four colours, that walk too has nothing to find and no way of knowing it.

The size of the obstruction is part of the difficulty. A clique of four is a certificate anyone can check: four points, six edges, done. The certificate that Grötzsch’s graph needs four colours is the whole failed search, or the recolouring argument applied to the five-cycle, and for the 47-point graph the search alone runs to nearly half a million partial colourings. Graphs whose colour count is forced by something small are easy to certify; graphs whose count is forced by everything at once are not.

Remove any edge and a colour comes free #

That impression can be made precise. A graph is critical for its colour count if removing any edge lets it be coloured with fewer colours. The search checks this for every edge in turn.

Every one of the 5 edges of the five-cycle, the 20 of Grötzsch’s graph and the 71 of the 23-point graph is critical, and Mycielski’s step preserves criticality in general. So there is no part of these graphs that is responsible for their colour count — no small piece that needs four colours by itself, as a clique would. The whole graph needs its colours, and remove any single edge and the need drops. It is the opposite of the situation the clique bound imagines, where a small dense piece forces the colours and the rest of the graph is free.

There is a limit to how dense such a graph can be. The edge that forces a triangle found that a graph on $n$ points with no triangle has at most $n^2/4$ edges, and the graphs at that limit are the complete bipartite ones, which need only two colours. Béla Andrásfai, Paul Erdős and Vera Sós proved in 1974 that more is true: a graph with no triangle in which every point has more than $2n/5$ neighbours is bipartite. So triangle-free graphs needing three or more colours must be sparse — and Mycielski’s are, each point of the 47-point graph having on average about ten neighbours.

One more colour each time, but less and less of one #

A fractional colouring relaxes the problem: instead of giving each point one colour, assign weights to the sets of points that could share a colour — the independent sets — so that every point is covered by total weight at least one, and minimise the total weight. The minimum is the fractional chromatic number. It is never more than the chromatic number and is often less, and it is computable by linear programming where the chromatic number is not.

For Mycielski’s graphs the two diverge. Michael Larsen, James Propp and Daniel Ullman proved in 1995 that the step adds to the fractional chromatic number exactly its own reciprocal: the five-cycle has fractional chromatic number 5/2, Grötzsch’s graph 29/10, and the sequence continues $f + 1/f$. That grows like the square root of twice the number of steps — about 5.39 for the graph needing fourteen colours — while the chromatic number grows by one at every step. Each new graph forces one more whole colour while adding less and less that a fractional colouring can see. The extra colours are, in a precise sense, a consequence of insisting that colours be indivisible.

Why the clique bound fails #

The clique is a local reason for needing colours: a few points all joined together, visible in a small part of the graph. Mycielski’s graphs need their colours for a global reason, a parity-like obstruction spread through the whole graph, and the proof that their colour count rises is a global argument about recolouring everything at once. The difference matters well beyond these examples. In how many colours the plane needs, the graphs that showed five colours are needed for the plane contain no large clique either; their need is again spread out, and they had to be found by search over thousands of points.

Paul Erdős pushed the phenomenon to its extreme in 1959. He showed, by choosing a graph at random and counting, that there are graphs in which every cycle is long — no triangles, no four-cycles, no short cycles of any length up to a chosen bound — and that still need as many colours as anyone likes. Such graphs look, locally, like trees, which need only two colours; every small neighbourhood can be coloured with two, and the whole cannot be coloured with a hundred. The proof gives no picture of any of them, only a guarantee that they exist; explicit constructions came later and are far larger than the random ones.

What the pictures cannot show #

The colour counts of the five graphs drawn are proved by exhaustive search — every partial colouring with one colour too few is tried and fails — and agree with the general argument. The search proves nothing about larger graphs in the sequence; the argument does. The claim that eleven points is the smallest for a triangle-free graph needing four colours is Chvátal’s theorem and is not checked here, since that would mean searching every triangle-free graph on ten points. The fractional chromatic numbers come from the Larsen–Propp–Ullman recurrence, not from solving a linear program for each graph, so the lower curve is a theorem drawn rather than a computation repeated.

The pictures also cannot show the 47-point graph, or any larger one, in a way that reveals why it needs its colours; drawn, it is a tangle of 236 edges, and the reason lives in the construction rather than in any view of the result. Even Grötzsch’s graph, small enough to draw, shows a colouring that works and not the 27 partial colourings that fail, which are the actual proof.

Still open: the smallest graph needing six colours #

The smallest triangle-free graph needing four colours has eleven points — Grötzsch’s, which is Mycielski’s — and the smallest needing five has twenty-two, found by Tommy Jensen and Gordon Royle in 1995, one fewer than Mycielski’s 23. How many points the smallest triangle-free graph needing six colours has is not known. Mycielski’s step gives one on 47 points, and better constructions do better, but the lower bound established by exhaustive computer search is well below the best construction, and closing the gap would require searching triangle-free graphs on more points than current methods can handle.

The difficulty is the one the search-cost figure shows in miniature. Proving that a triangle-free graph on, say, thirty-odd points cannot need six colours means ruling out every graph of that size, and proving each graph’s colour count is itself hard, because the obstruction is global. The gap between what Mycielski’s simple step builds and what is optimal has been closed at four and five colours by search, and at six it is still open.