Nine points will do

Share this page
Sep 2001

To show that, even with only nine points, there must be either a blue triangle or four points connected by red lines, we need a subtle improvement on the reasoning we used for 10 points.

With 10 points, the proof relied on finding a point connected either to at least six red lines, or to at least four blue ones. Once we had such a point, we could be sure to find our three friends or four strangers. And in fact, by counting the lines meeting at a point, we saw that any point would do.

If the graph has only 9 points, each has only 8 neighbours. How can our theorem fail? Only if every point has exactly five red lines and three blue ones. That is, every point must look like this:

How many blue lines would this annoying graph have? Well, every line has two ends, and three blue lines meet at each of the 9 points. So the total number of blue lines is (9×3)/2, which is 13.5. Oh dear! This is impossible - of course there must be a whole number of blue lines in the graph.

So there must, after all, be at least one point connected to either four blue lines or six red lines, and now the same argument as before shows there must be three friends (a blue triangle) or four strangers.

  • Want facts and want them fast? Our Maths in a minute series explores key mathematical concepts in just a few words.

  • The BloodCounts! project is gearing up towards one of the largest-scale applications yet of machine learning in medicine and healthcare.

  • What do chocolate and mayonnaise have in common? It's maths! Find out how in this podcast featuring engineer Valerie Pinfield.

  • Is it possible to write unique music with the limited quantity of notes and chords available? We ask musician Oli Freke!

  • How can maths help to understand the Southern Ocean, a vital component of the Earth's climate system?

  • Was the mathematical modelling projecting the course of the pandemic too pessimistic, or were the projections justified? Matt Keeling tells our colleagues from SBIDER about the COVID models that fed into public policy.