Fun Fact - The Hadwiger Nelson Problem

You know what's cool about mathematics? We can pose a problem that a junior high student can understand, yet nobody knows the answer. Here is an example. It is called the Hadwiger Nelson problem, after its creators. How many colors are needed to color all the points of the xy plane, so that no two points, 1 unit apart, have the same color?

Two won't do, as shown by an equilateral triangle in the plane, 1 unit on a side. Each corner is a distance of 1 from the other 2, hence you need at least 3 colors.

Three colors won't do, as per the following argument. Paint the origin red, and designate 2 points orange and yellow on the unit circle, forming an equilateral triangle. Draw a bisector through this triangle out to a radius of sqrt(3). That point produces another equilateral triangle with orange and yellow, and it too must be red. Every point on the circle of radius sqrt(3) is red, and that is impossible, as shown by any two points on that circle that are 1 unit apart.

If you extend this problem to higher dimensions, coloring all the points in n-space, then the above construction, i.e. painting the origin and the entire hypersphere of radius sqrt(3) red, shows n+1 colors are not sufficient.

If you tile the plane with well-defined regions, like coloring in a coloring book, then the minimum is 6. We don't know if there is a 6 color solution, but there is a 7 color solution, which I will describe below. Four or five color solutions might exist if the plane is fuzzy, i.e. just a smear of different colors no matter how powerful your microscope.

7 Colors

The base cell is a regular hexagon, ½ inch on a side. (Make it just a hair less than ½ if you want some wiggle room.) The diameter of this hexagon, from one corner to the opposite corner, is 1, hence it can be colored with one color. Tile the entire plane with these hexagons. Hexagons point up and down. As we move along one row of hexagons, color the cells red orange yellow green blue indigo violet, and repeat. The row just above this one is colored the same way, but shifted ober, so that the red hexagon rests above yellow and green. The row above this is colored the same way, with the same phase shift. This pattern repeats as successive rows tile the entire plane. Verify that the closest red hexagons are sqrt(7)/2 = 1.32 inches apart. Therefore points that are 1 unit apart always have different colors.

The 7 color hexagon tiling is regional, i.e. small regions of the plane are assigned individual colors and it all works out. Any regional solution requires at least 6 colors. Let's see if we can prove that, and in the process, put some constraints on a 6 color solution.

Definitions

A region is an open connected set, and its border is, well, its boundary. Borders are piecewise smooth, so that they almost look straight at a microscopic scale. Each region is assigned one color, and each border point has a color that matches one of its adjacent regions. We'll see that the borders are not important; if we can make the regions work, we can make the borders work.

The diameter of a region cannot exceed 1, else 2 points somewhere along the path from one end to the other would have the same color and be 1 distance apart. Show this by the intermediate value theorem, as the distance along the path ranges from 0 to something greater than 1. Thus regions can only be so big. We saw this with our hexagons. I chose hexagons with a diameter of 1, or something slightly less than 1, so that borders are not an issue.

Suppose a border between red and yellow bends at a point p. Remember, the border only has to be piecewise smooth, so it can turn sharply at p, forming a corner if you will. We are small, so the border is linear, looking like to segments that meet at p at some angle, such as 170 °. The yellow side is 170, the red side is 190. Draw an arc with curvature 1 connecting the 2 segments on the yellow side, thus smoothing out the bend. Everything between the arc and the angle can be painted red. If q is such a point, and if q is 1 point away from a point r, then a circle centered at r already intersects the red region, so r could not be red. There is no trouble painting q red. Leave the arc, the new border, yellow if you like, it was yellow before, or make it black because borders don't matter. Points that were on the border between red and yellow, including p, can be painted red. After this transformation, all borders are smooth.

In the same way, a border with curvature greater than 1 can be smoothed out to curvature 1. There is no need to turn faster than the unit circle.

A point p is a vertex if at least 3 regions meet at p.

Suppose two red regions meet at a vertex p, showing an angle of less than 180 °. Put p at the origin, and let red lines meet at p, with the y axis as their bisector. The story is almost the same as that shown above. Draw an arc through the yellow region just above p, and paint everything strictly between this arc and the red regions red. The only trouble might be the pesky point p, which gives us a means of escape. In other words, q, trapped below the arc, could be one point away from a red point r, with the circle c centered at r passing through q and p. However, if r is red then it is part of a red region. A red disk contains r, and those points collide with the red points near p. this is a contradiction. Each q between the red regions and the arc can be painted red, and the two red regions merge into one. Assume this has been done wherever possible. Therefore, if two red regions meet at p, they present angles of 180 ° on either side. The regions come to infinitely sharp points at p, and are called needles.

A region at a vertex is normal if its angle is greater than 0 °, or a needle if its angle is 0 °.

Three red regions cannot meet at p, thus every vertex has finitely many incident regions. You can count them off in a counterclockwise direction.

Borders

We can leave the borders black, because any regional solution extends to the borders. If p is on the border, give it the color of the region directly to its right. If a border, i.e. a line segment, enters p from the right then assign it the color of the region just above this line. this assignment is unambiguous, and can be done throughout the plane in one go.

Assume p is colored red, and suppose r is 1 unit away and belongs to a red region. Since r is in the interior of a red set, some disk about p is not red, and p would not be colored red. Suppose r is on a border and it too is colored red. Red points approach r from the right, or from the right and just a hair above. With these in place, red cannot approach p from the right. This is a contradiction. the border has now been colored consistent with the regions. Thus we can simply color the regions, i.e. the open sets, and leave the borders black.

Needles

Let p be a vertex with a red needle pointing up from below. This needle curves away from p, to the left or the right, or both if the left side curves left and the right side curves right. If both sides curve right then reflect the picture. Now we know the left side curves left, with curvature at most 1. The border of this needle may trace a circle of radius 1, or it may be a little straighter than such a circle. If the right side also curves left its curvature is less than 1, or becomes less than 1 as soon as it leaves p. It is straighter then a circle of radius 1.

Let c be the unit circle about p. The area just inside the top half of c can't be red, and the area just outside the bottom half of c can't be red. Let q be 1 unit to the left of p and let r be 1 unit to the right of p. These are transition points. The points along the qr line, just inside c, arbitrarily close to q and r, can't be red. This is obvious near r, but takes a bit of thought near q. A point just to the right of q is the center of a unit circle d that just misses p. This circle curves faster than the right side of the needle, so even if that edge curves left, d crashes into it. Thus the points just to the right of q cannot be red. By a continuity argument, or more brute force geometry, a small area just inside c, near the points q and r, can't be red. This non red area straddles c below, then moves up along the inside of c, crawling across q or r. Put this altogether and a continuous band of nonzero thickness runs along c, inside above, outside below, and inside near q and r, and this band cannot be red.

If there are 2 red needles above and below, then reflect this band vertically and paste it on top of the original. Now a continuous non red band of nonzero thickness runs along c, inside and outside of c all the way around, except for the qr line where the band is inside only. Red can only approach c at q and r from outside.

Return to 1 red needle from below, with its corresponding non red band inside c above, straddling c just below q and r, and then outside c below. ASsume red does not approach r from the right. (Red can't approach r from below or from inside c.) There is a small disk about r that is not red. It is possible to paste a tiny red triangle onto the right side of the needle pointing up at p, thus creating a normal red region at p. The triangle may have to be very small, and highly acute, if the non red disk about r is small. Apply the same reasoning that we've used before. Is there a point in this triangle that can't be red, because there is another red point one unit away? Let k be a point in this triangle and imagine a unit circle d passing through k. If d intersects the needle then its center cannot be red. Thus d is nearly vertical through k, and its center is near q or near r. Points near r are not red, so d curves left. Its center is near q, but still to the right of q, and that can't be red either. In other words, d curves faster than the right side of the needle, and crashes into the red needle. There is no trouble coloring this triangle red, along with the gap between the needle and the triangle, if both edges of the needle curve left and there is such a gap. Similar comments apply if red does not approach q from the left.

Assume we have thickened needles into normal regions wherever possible. If a red needle persists then red approaches both q and r from the left and right respectively. These red regions could head straight up from q and r, but they can't lean in at a proper angle, because that would cut into c, and the band just inside c, above q and r, cannot be red. By the same reasoning, they can't lean in towards c as they travel down from q and r. Even moreso, since the band outside of c, below q and r, cannot be red.

If the red needle curves left with curvature 1, then the red region at q cannot descend straight down. If we head straight down from q, and curve left with maximum curvature 1, in parallel with the needle at p, then red points will be 1 unit apart. The angle is away from vertical whenever the red needle has curvature 1.

Similar exclusion bands can be drawn for a normal region at p. If the angle is 20 °, symmetric about the y axis, then the transition points q and r climb 10 ° up the unit circle c. A continuous non red band runs around c, inside from r to q above, outside from q to r below, and inside near the points q and r.

Turn the entire picture 10 ° clockwise for convenience. This puts r back on the x axis. The red region runs straight down vertically from the origin. Assume it does not curve left with curvature 1. (This was the case when the region was a needle.) Further assume red does not approach r from the right. We can paste a small acute triangle to the right of the red region at the origin. The reasoning is the same as that shown above. Thus the region has been "enlarged". If it will help, we can enlarge any region at its vertex p, unless it curves inward with curvature 1, or there are points of the same color approaching a point r 1 unit away from p and perpendicular to the border.

Let the red needle have green on the left and yellow on the right. Green slides up along the needle, almost like another needle. Build a non green band around c, as we did with red. The inside of the upper half of c is non green, and the outside of the lower half of c is non green. q and r are transition points. Here is a difference though, green could approach q from the right. If it does, coming in to q at any angle, even vertical along the inside of c, the red green border has to follow a circle centered at q. The needle attains its maximum curvature of 1, and remains so as long as the green red border exists. Of course this need not happen; green might not approach q at all, whence the needle need not have curvature 1.

On the other side, green cannot approach r from the left, just as red could not approach r from the left. r is a transition point and not a choke point.

One could imagine green descending straight down from r; its curvature to the left is at most ½. If the needle has curvature 1 to the left, green is just inside a unit circle centered at q, and green must stay outside a circle of radius 2 centered at q; that's where we get curvature ½. If the needle's curvature is w, green stays outside of an arc descending from r, with curvature w/(w+1). The curvature could be 0, a green wall descending from p, and perhaps another one descending from r. With this in mind, the band is non green just outside of c and below r. Some other color, not red green yellow, meets r just outside of c.

If green approaches q, the green at q is not a vertical needle pointing up at q, as its left edge curves 1 to the right, and its right edge would curve faster than 1. If it runs vertically down at q it is anormal region down and to the right of q. It could be a needle poking in from the right however, or even a normal region entirely above the x axis. It can't run straight up from q however, as that would be in range of the green region just to the left of the red needle at p. Green rises at some positive angle relative to vertical. In the same way, if the green border runs down from q, it can't extend straight up at p. If green continues straight up past p, then green comes to a point at q.

2 Color Trouble

Suppose there is a 2 color band thatravels along c for more than 120 °. It may weave inside and outside of c, straddling c in some places. Assume the band is orange at the start. Draw a path in the band, from one end to the other, traveling counterclockwise, so that the angle, relative to p, is strictly increasing. The radial distance can slide in and out to remain within the band, but is always near 1, i.e. close to c. Let y be the first point on the path where orange changes to pink. Let z be the point approximately 60 ° over from y, such that y and z are one unit apart. Draw the arc through z centered at y. Points inside this arc are pink and points outside this arc are orange. In the same way, draw an arc through y centered at z. Points inside this arc are pink and points outside this arc are orange. The 2 arcs bend towards each other, and that brings orange points within 1 of each other. This 2 color arc cannot exist.

The same thing happens in a pink orange band that is exactly 120 °, as long as the middle of the band is outside of c. You will encounter y, at most 1 unit away from start, before 60°, and then you encounter z, 1 unit away from y before the end of the band.

2 colors along exactly 120 ° on the inside of c is no trouble though, as shown by 6 pieces of pie having 6 colors around. As you travel around, you find y at less than 60 °, but not z. the orange pink border could be perpendicular to c, or it could lean one way or the other, but not more than 30 °. If it slants too far twards pink, for example, then orange points at the border are 1 unit away from points on the other end of the orange region.

This result disappears if choke points are strategically placed. Draw a 60 degree orange region straddling c, somewhat like a football, then a 60 degree pink region, then a 60 degree orange region. That's 180 ° of orange and pink. The 2 points demarking pink are choke points. The orange pink restriction does not apply at these two points - not inside of c and not outside of c. If it did, there would be 2 color trouble. We can even have 6 regions orange pink orange pink orange pink running all the way around, with 6 choke points forming a hexagon. This is an anomaly; 2 color annuluses are usually impossible.

Sometimes the arc is less than 120 °, yet we can still find trouble. Let y and z, in the interior of the arc, (i.e. not the end points), be 60 ° apart, with pink approaching y and z from within. That means orange approaches y and z from without. Draw the circular pink orange borders as before, and orange points will be within 1 of each other. There could be choke points along the way, as long as they aren't y and z. In fact we only need tiny (arbitrarily small) pink orange 2 color bands at y and z. If the regions are both inside c or both outside c, the borders pull the orange regions too close together. If one region is inside c and one outside c, the borders pull the pink regions too far apart.

2 Color Thickening

Consider a 2 color arc, inside or outside of c, > 60 and ≤ 120. There are no choke points. It is orange at the right, and 60 ° over it has to be pink. Pink could start earlier but it must be extant at 60. Slide both points counterclockwise t ° until there is a color change. Pink becomes orange and orange becomes pink. These are points y and z, still 60 ° apart, and they produce the trouble described in the previous paragraph. Thus this color change cannot occur. It's pink all the way to the other end of the 2 color band. If the arc length is 80 °, then 20 ° on one end is orange and 20 ° on the other end is pink. We don't know what happens in the middle - could be a series of pink and orange stripes. Could be orange pink orange pink, each 20 °.

The right is not just orange along c and pink a little bit away from c, for that would still be in range of pink on the left. No, it's solid orange on the right and solid pink on the left, for t-60 °.

No 4 Color Solution

If there are only 4 colors, let p be any point on a red yellow border. Draw a circle c about p. A band runs along c for 180 ° and is restricted to 2 colors. This is 2 color trouble.

Lopsided

Suppose two colors consume 60 ° or less. This is called lopsided. Let a circle just miss p and cut through these 2 colors and the colors on either side. this circle pivots about p, 60 ° one way and 60 ° the other. This defines a 2 color region outside of c with arc at least 120 °. That is impossible, hence we can rule out any lopsided arrangements.

Two adjacent needles would consume 0 °, which is lopsided. Needles cannot be adjacent. Nor can a needle be next to a region that is 60 ° or less. Nor can two needles be within 60 ° of each other.

If 3 colors consume less than 120 ° that is also lopsided. An inside region, or outside region, as you prefer, of more than 60 °, is 1 color, and that can't happen. Even 120 ° can be a problem in some situations. Suppose the borders are straight lines, and build a one color arc on the inside of c. Look at the end of this 60 degree arc. A circle just grazes p, with its tangent line parallel to the straight border, and yet it cuts through all 5 colors. The one color arc doesn't taper to a point, it still has thickness, thus it is more than 60 °. Three colors can consume exactly 120 ° only if the two outer borders curve away from the three colors, with curvature 1.

Finally, 4 colors consuming less than 180 ° is lopsided. A circle cuts through them, and the other 2 colors, and the center of said circle exhibits the seventh color. This could happen without the previous 2 conditions; if each region is 44 ° then each pair of regions is 88 and 3 in a row are 132.

p is also lopsided when 4 regions consume exactly 180 °, and 2 regions are on the other side, and one border or the other fails to curve toward the other side with curvature 1. Example: straight lines and angles of 45 45 45 45 90 90. A circle grazes p, parallel to the straight line, and cuts through all 6 regions.

In general, 4 regions consuming 180 becomes lopsided if either of the borders fails to have curvature 1 after a time. It may start out a perfect circle, but then it drops back. Put 4 regions below the x axis, and let the 2 borders curve upward, looking like a circle tangent to the origin and centered at 0,1. Suppose, after a time, the right border falls back, showing curvature less than 1, or even becoming a straight line. Let d be the circle tangent to the origin. Lower it by the tiniest ε. Now d is tangent to 0,-ε. Pivot the circle about this tangent point to the right, through the tiniest angle. It cuts through all 6 regions, and its center attains the seventh color.

By the same reasoning, 3 regions consuming exactly 120 ° is lopsided unless both borders curve away from these 3 regions with curvature 1, for as long as those borders exist.

The lopsided criteria ratchet back if we only allow 5 colors. No region 60 ° or less, no two adjacent regions < 120, and no 3 regions < 180.

Annulus Around 3

Let red yellow and green meet at p, with the red yellow border heading straight up. We can build an annulus around p that is not red yellow or green - except for a few choke points. Some of the regions run along the outside of c, some along the inside of c, and some straddle c.

Assume the red yellow border has no curvature, a straight line. There should be a choke point r, 1 unit to the right of p, but watch what happens. A circle d has its center just to the left of r. It grazes p, and because the border above p is straight, it cuts through all three regions. The area to the left of r is not red yellow or green, and r is not a choke point. It is a transition point, but not a choke point. Traveling counterclockwise, the band runs along the inside of c, up to and just past r; and starting at r the band runs along the outside of c. It straddles c just above r.

Yes, r could be a choke point if the red yellow border curves to the right with curvature 1, but then the point q, diametrically opposed to r, is not a choke point. There are at most 3 choke points, and there may be none, e.g. when all three borders are straight lines.

If one of the regions is less than 120 °, the implied bands, one inside c and one outside c, are more than 60 °. Assume all three regions are 120 °. The band below r and inside c is 60 °. Assume, without loss of generality, that the red yellow border goes straight up or curves left. Now the inside band continues past r and is more than 60 °. There is always an inner band that is more than 60 °.

2 Color Annulus

Assume an annulus like the one described above. Then suppose it is restricted to pink and orange. Perhaps we only have 5 colors, or perhaps we allow 6 but red needles point up and down at p, with 3 normal regions at p.

We will show a contradiction by walking around the annulus. Each 6 steps forms an almost hexagon and moves you just a little ahead of where you were before. Colors alternate, so after 6 steps the color is the same. Yet the point advances around c, and eventually the color must change.

Find a band inside c that is more than 60 °, and use 2 color thickening. Put the point s on c near the beginning of this band, bordering a solid orange region. Let s seed a hexagon around c. Rotate it if need be, to avoid the choke points of c. Adjust the hexagon again, so none of its points are on a pink orange border as the map has been colored. Now we're ready to start.

The band from s to s+60.1 ° has a certain thickness inside c, and is continuous on a compact space, thus it attains its minimum. Call this thickness t. You can think of the band as a strip of width t if you like.

Move s a hair inside c, and move the other 5 points of the hexagon inside or outside of c, staying within their bands, and jiggle them just a bit so that each is 1 unit ahead of the previous. After 6 steps, the seventh point doesn't land on s any more, but by keeping the points of the hexagon close to c, it can land very close to s. These points are orange pink orange pink orange pink and finally orange again, in the same region as s. Move the inside points farther in than the outside points move out, so that s7 lands just a hair ahead of s1. We have made progress.

Take another 6 steps and make more progress. Each cycle, comprising 6 steps, advances the point in the orange region counterclockwise along c. This progress need not shrink to 0, in zeno's paradox, because the orange region has a thickness t. We can always keep the sixth point a tiny bit away from c, and advance by some angle δ. So we step, slowly but surely, towards the orange pink border.

Finally, take another 6 steps and land in the pink region next to the orange region. However, this point must still be orange. This is a contradiction, hence the pink orange coloring cannot exist.

I'm glossing over something here; what if there is no "next" pink region? What if infinitely many pink and orange stripes shrink to infinitely thin regions, as they approach the end of the orange region? Then there is no next region. There are other reasons these stripes cannot exist, but even if they did, you could step through just the right angle, to land inside a pink stripe, and obtain the same contradiction. Or, keep going until you reach the solid pink end of the band.

It's interesting to watch what happens with 6 footballs around the circle, 6 regions of 60 ° each, orange pink orange pink orange pink, all separated by choke points. Pick s in an orange region, just inside c, and take 6 steps around, and wind up just ahead of s. Do this again and again, but Zeno comes to haunt you. All the points in your path approach choke points, and are forced closer and closer to c. The advance becomes smaller and smaller, as s approaches the next choke point. You never jump into the next region, and there is no contradiction.

No 5 Color Solution

If 3 regions meet at a vertex we have a 2 color annulus, which doesn't work, as described above. Hereinafter, 4 or 5 regions meet at each vertex.

Put 4 regions at p, each region more than 60 ° to avoid lopsided. Suppose regions run red yellow blue green counterclockwise around p, with red at the bottom. Orange is the fifth color. Arrange things so that red + blue is no more than 180. both are greater than 60, so both are less than 120. Let the angles be s t u v around, with s and u strictly between 60 and 120. Look at the arc of c above p. Outside is orange or red for 180-u °. Inside is orange or blue for 180-s °. It's a bit of work to demonstrate the overlap.

Center red about the y axis. Angles are measured from the positive x axis counterclockwise in the usual manner. The inner band runs from ½s to 180-½s. The outer band runs from ½s + t + u - 180 to ½s + t. tilt your head and subtract ½s. The inner band runs from 0 to 180-s. The outer band runs from t + u - 180 to t. Assume, without loss of generality, u ≥ s. If u+t and u+v are both < 180 then 2u+t+v < 360, whence s+t+u+v < 360, which is impossible. Reflect if need be, so that u+t is at least 180. Now t+u-180 is at least 0. The overlap runs from t+u-180 to 180-s, or t, whichever is shorter. t - (t+u-180) is 180-u, which is greater than 60. Or, (180-s) - (t+u-180) = 360-(s+t+u) = v. Remember that v > 60. Either way we have an overlap of more than 60 °. 2 color thickening applies.

Start at the right and proceed counterclockwise until the color changes. If we start with red and blue, and one changes to orange before the other, or they both change at the same time, we have a vertex with 3 colors, which is impossible. thus one or both regions starts out orange. Start with double orange. If inside becomes blue and outside becomes red at the same time, we have a vertex with 3 colors. One of them changes before the other. Suppose inside changes to blue first; outside is still orange. Orange inside can't come in at an angle, it has to look like a needle running along c, but its curvature, bent inward by c, is greater than 1, so that is impossible. So outside changes to red first. It has to change back to orange, and we're back to double orange. Eventually orange inside changes to blue, a contradiction. Next start with red outside and orange inside. Orange can't change to blue, or we have a 3 color vertex. Red changes to orange, which is double orange, which we already covered. Finally start with orange outside and blue inside. Blue gives way to orange, and we have the same orange curvature problem we saw before. Therefore 4 colors do not meet at p.

The last case is all 5 colors at p. Let them run red yellow blue orange green around. If red + yellow is 140 ° (to illustrate), then a 40 degree arc of c is orange inside and red or yellow outside. Can't be both red and yellow, else we have a 3 region vertex, so pick one, say yellow. Tick around c counterclockwise and color the next adjacent arc. If orange + green is 150 ° (to illustrate), then a 30 degree arc of c is yellow outside and orange or green inside. 40 + 30 is 70, which is the angle of blue, which is guaranteed to be more than 60. Yellow points are 1 unit apart. That's the last case; there is no 5 color regional solution.

I work on this problem from time to time, looking for a 6 color regional solution or trying to disprove. I have ruled out a few cases here and there, like red and blue needles pointing at each other, but I'm not sure this brute force approach will produce an answer. if you wish.

Needle Neighbors

Assume 3 regions consume less than 180 °. These are green red yellow counterclockwise, approaching p from below, with red symmetric about the y axis. The neighbors are orange and pink, hence there is a point z, one unit away from p, demarking an inside band that is blue. Draw a bisector through the green red yellow conglomerate and extend up to c to find z. Travel counterclockwise from z, inside c, and find a blue pink band, until you are perpendicular to the left border of red. similarly, a blue orange band procedes clockwise from z, until you are perpendicular to the right border of red. Let these bands be t and s degrees respectively. The overlap near the top, that is guaranteed to be blue, is o degrees, which is 180 - (green + red + yellow). t = 180 - (red + yellow). s = 180 - (green + red). Assume s and t are greater than 60, so that 2 color thickening applies. Blue at the top is at least s-60 + t-60 - o. This is 60 - red. The two bands combined are 180 - red.

this is especially useful when red is a needle, at 0 °. Green or yellow can't be 60 or less as that is lopsided. That means green + red and yellow + red are both less than 120, as we stipulated. The two bands combined run from r around to q inside c, while their counterparts run from q around to r outside c. The effective blue band (after coloring) is 60, and can't be more. If blue is not perfectly centered at the top of c, with the red needle pointing at its center, a resulting 2 color band is more than 120, and that is trouble. z may not be at the top of c, but blue extends on either side of z, such that it is centered about the y axis. Orange fills in the right band, and pink fills in the left band. This is possible, as long as the orange blue border and the blue pink border don't slant more than 30 ° from normal. However, it is not possible on the bottom half of c. Restrictions on the inside along the top half of c imply the same restrictions on the outside along the bottom half of c. We've seen this before. There is an effective 2 color band of at least 120 °, and that is trouble. Therefore, a red needle does not have neighbors comprising less than 180 °.

You might wonder about neighbors that sum to exactly 180 °. z is now a transition point, and could be a choke point if the yellow orange or pink green border curves upward. The point w, opposite to z, is definitely a choke point. Points just inside of z, or outside of w, are orange blue or pink. Bands are more than 60 °, and thickening still applies.

If blue is at the top of both bands, approaching z from either side, configuration 1, then orange and pink complete the bands as before. blue fills in the gap at z. This is possible inside, but switch to the outside and look for trouble. Travel through the orange blue band, and past w, and into the pink blue band. The 2 thickened blue ends sum to 60, with w between them. Orange and pink complete the bands. Orange and blue span 120, which should spell trouble. Yes, there is a choke point w, but blue is on either side of w, so the change from orange to blue happens within 60 ° of w, and then we vault past w for the change from blue back to orange, which can't happen. Therefore, we can't have configuration 1 on the outside.

Now suppose blue meets orange at z, configuration 2, while pink, the third color, does not approach z. There is a proper blue orange border at z. The choke point has disappeared. There must be another blue orange border 60 ° over from z. Whether inside or outside, this is trouble.

Let pink approach z, as a needle or as a normal region. Two pink regions can't approach z, so it's blue pink orange pivoting around. Let y be z + 60 ° around. Because pink and blue both approach z, y is a change from blue to pink. Pink points are pulled towards each other at y and z, and that is a contradiction. this happens inside or outside. Configuration 2 doesn't work.

Finally put blue at q and r, while orange meets pink at z. This is configuration 3. If blue approaches z, then combine this with the blue orange change at z-60, and blue points are pulled toward each other. Thus we have an orange pink border at z. This is possible, if regions run blue orange pink blue around, at 35, 40, 50, and 55 degrees, for example. When you color these regions, don't let orange + pink exceed 120 °, or you have 2 color trouble. By thickening, the blue regions at q and r sum to at least 60. Remember that z, demarking the orange pink border, need not be at the top of c, its location is determined by the green red yellow border line that forms vertical angles with the red needle.

Configuration 3 is the only one that works on the outside, along the bottom half of c. If we try 3 along the top as well, then blue is below and above r, and blue is below and above q. Each side is limited to 60 °. Yet the sum of the 4 blue regions is at least 120 °. Each blue region is the thickened end of its band and no more. Below, and on the outside, the orange pink band is 120 °, and that is trouble. We are left with configuration 3 below and configuration 1 above. Starting at r, regions might run: orange 60, blue 60, pink 60, blue 45, orange 45, pink 45, blue 45.

At the top of c, on the inside, configuration 1 is forced unless the yellow orange border, and the green pink border, both curve upward with curvature 1. Without this curvature, circles can just skirt p, and force blue points arbitrarily close to z.

2 Red Needles

If two red needles point at each other, we will show that one side is one color (180 °) and the other side is another color. No other configuration can exist.

Suppose a blue needle points at p and makes an angle of less than 120 ° with the red needle. With the color between, this is lopsided. There is no room for a blue needle anywhere. All other regions are normal.

A needle cannot be next to a region of 60 degrees or less, as that would be lopsided. If 2 red needles have green and pink on the left side of p, green and pink are both more than 60 degrees, and of course less than 120.

If 2 red needles have yellow blue orange on the right, in that order, yellow cannot be 60 or less, as that forces a lopsided configuration. That leaves blue orange red less than 120, which is lopsided. We can't have 3 colors on one side, and 4 would be even worse. Each side has 1 or 2 colors.

If green is on the left then we have yellow or yellow blue on the right. The second case creats a 2 color annulus, so we can rule that out.

Place green and pink on the left, and yellow and orange on the right. Blue is the leftover color. Suppose pink + orange consumes less than 180 degrees. This produces the needle neighbor contradiction described in the previous section. If the angle is greater than 180 we find the same contradiction using the needle below. Therefore pink + orange = 180, and p looks like vertical angles. Neighbors sum to 180, above and below. We have configuration 3 on the outside of c below, and also configuration 3 on the outside of c above. Blue regions lie above and below r, and above and below q. We saw that this leads to a contradiction. That completes the case of red needles and 2 colors on either side. The only case left is the aforementioned green on the left and yellow on the right.

Two Vertices within 2

Let y and z be vertices less that 2 units apart. Each vertex has 3 adjacent regions, and together, all 6 colors are represented. Draw a circle c about y, and then the annulus that cannot be any of the 3 colors incident to y. Remember, c has at most 3 choke points, according to the 3 borders at y. Draw a circle d about z, and then the annulus that cannot be any of the 3 colors incident to z. If the two annuli have a measurable overlap, it must be the seventh color, which is impossible. This can only be avoided if c and d intersect in 2 choke points for both circles. This seems highly unlikely, but it is nonetheless a case that you have to rule out.

Red Blue Needles Up and Down

Let a red needle point up at p, and let a blue needle point down at p. Three colors on one side is lopsided, as we saw in the previous section, so put 2 colors on one side and 2 colors on the other. The neighbors of the red needle cannot sum to less than 180 °, nor the neighbors of the blue needle. Each sums to 180, and p looks like vertical angles. Adopt the colors of the previous section, thus regions run red(needle) yellow orange red(needle) pink green around p.

Start at r and travel counterclockwise along c. Find orange inside, for 60 °, and red outside, for a span no larger than 60 °. Below r is yellow and blue. The outside colors extend no farther than the inside colors. Let red stop at y on c, thus y is a vertex with orange red green (and perhaps blue) around. Let blue stop at z on c, thus z is a vertex with pink blue yellow (and perhaps red) around. These are vertices within 2 of each other, as described in the previous section.

Draw circles around y and z and let them intersect in u and v. u is equal to p, but v is to the right of r, perhaps up or down. Two of the three borders at y are defined by c, and these cannot make v a choke point. The same is true at z. If the remaining borders do not make v a choke point then the conditions of the previous section apply. Let's seee what happens.

Put y at +60 °, while z is above -60 °. Thus v is above and to the right of r. because red spans 60 ° from r to y, the green red border at y has to lean right; it has to be 30 ° to the horizontal or less. If it is exactly 30 ° it curves downward in a circular arc. The choke point defined by this border is r, or something below r. It is not v. Pull v down and away from y, in a pivot about z, and find a region that is not orange red or green. wiggle it a bit and you are inside a region that cannot be pink blue or yellow. This is a contradiction. Therefore, y and z are both 60 ° from r, or they are both closer than 60 ° from r.

Let y and z be 60 ° from r. If only red and blue approach r from the right, then we have an outside red blue arc of 120 °, and that is 2 color trouble. Some other color separates red and blue. In fact, some other color approaches r from the right along the x axis. It can't be yellow, or orange, as that would collide with the bands on the inside of c. If green is adjacent to red, then it is too close to green on the other side of red just above y. We need pink to act as a buffer between green at r and green at y. There are 6 regions at r, and they run blue green pink red orange yellow around.

With 4 regions on the right side of r, and 2 on the left, you might think this is lopsided, but the 2 borders are perfect circles, as defined by c. Similarly, the needles, with 2 normal regions on either side of p, show perfect circular borders with their neighbors, starting at p, for as long as those borders exist.

Red touches r from above, and has a certain angle with the x axis. If this angle is less then 30 degrees, then measure the distance to y and find red points 1 unit apart. The pink region reaches 30 ° or more, and green reaches -30 ° or more. If they stop at 30 ° they both curve away from the x axis.

If pink + green is 60 ° or less then we are lopsided. This is a confirmation of the previous paragraph. In fact somebody (pink or green) has to go beyond 30 °.

The green red border at y has to lean right; in fact it has to be 30 ° to the horizontal or less. If it is 30 ° it curves downward in a circular arc. r is 1 unit away from y, and the green pink border can't be higher than 30 ° from the x axis. If they are both 30 °, green curves downward at y with curvature 1, as we already stated, and green could curve downward from r as well, but green points will still be 1 unit apart. Parallel circular arcs don't work. Therefore, the pink green border has to be lower than 30 °. We already said the pink red border has to be 30 ° or more, thus the pink region is normal. We expected this, since it is a buffer between green at r and green at y. By symmetry, green is also a normal region at r.

On the other side of r, the orange yellow border is within 30 degrees of normal.

If the green red border at y leans lower than 30 °, then green collids with the green region at r. Thus the green red border at y procedes exactly 30 ° from horizontal, and curves downward with curvature 1, for as long as the border exists. By symmetry, the pink blue border at z procedes exactly 30 ° from horizontal, and curves upward with curvature 1, for as long as the border exists. This is not surprising; v = r, and if this is a valid coloring, then v is a choke point relative to both y and z.

Suppose red is a needle pointing down at r. By needle neighbors, pink + red + orange is at least 180. Let d be the circle centered at r. We already said the orange blue border at p, i.e. the right side of the blue needle, curves right with curvature 1 for as long as the border exists. This is the path of d. The outside of d has a green blue band from p traveling clockwise up to 180-s, where s is the angle of orange at r. With orange at most 120, this band is at least 60, from p to y. It is blue at p, and blue at y inside c, and green at y outside c. The blue green band continues a bit past y, even if not prescribed. At or some time past y we may encounter a blue green yellow band, then switch to a blue yellow band. The fun ends when we point perpendicular to the right edge of the blue region at r. The blue green border is at least 30 ° from the x axis, so our bands run at least 60 ° along d clockwise from y. With green directly above y, we can't have green for 60 ° along d. Green cannot change to blue because that creates a blue green blue band along d, but at some point green changes to something, so green changes to yellow. A green yellow band runs along the top of c for 60 °, then along the top of d for a time, where it changes from green to yellow. Back up to a point above c, 1 unit away, where it changes from yellow to green. This is 2 color trouble. Therefore, we have no needles at r. The pattern does not simply repeat along the x axis.

Continue the above, but red is a normal region at r, of at most 60 °. Start at p and travel clockwise around the outside of d. The band starts out blue green or pink. By the time we reach y, or sooner, pink is forbidden. Some time after y, yellow is ok. Before we reach y + 60, perhaps just before, green is forbidden. Travel across the top of c, then the top of d, and yellow changes to green, but green cannot change to yellow. We saw this in the last paragraph. It must change to blue. Back up along d, so you are 1 unit away from the green blue border. It can't be blue changing to green; we need some pink. this pink region is on the outside of d between p and y. Move 1 unit to the left and run into a pink region on the inside of c. This is a contradiction. That completes the case of y and z 60 ° from r.

Now y and z are less than 60 ° away from r. (The same thing happens on the left side of c.) Let k and l be the points on c that are 60 ° away from r. k is green blue orange around, and l is pink yellow red around. The potential choke points are p and r. p is choke by the circular arcs of c. r could be a choke point if the orange blue border and the yellow red border lean 30 ° off normal from c and curve toward r. By symmetry, the blue pink border and the green red border lean 30 ° off normal from c and curve toward q.

Return to y and z, above and below r on c. These are once again 3 color vertices, consuming all 6 colors, so we are looking for choke points. p is a common choke point, thanks to c. v is to the right of r, somewhere near the x axis. It could be a choke point for both if the red green border and the pink blue border are just so. They curve away from c and toward the x axis.

Now push k another 60 ° around, so it is on c with yellow outside and blue and pink inside. y has orange inside and red and green outside. p is a common choke point thanks to c. The other point 1 unit away from y and k floats above c. Since the borders all curve toward the x axis, this is not a choke point, and is therefore the seventh color. This is a contradiction, and it completes the case of 2 colors on one side and 2 colors on the other.

Put one color (green) on the left and two colors (yellow and orange) on the right. Remember that yellow and orange are each more than 60 °. Starting at or near the top of c, at a point y, on the inside, and traveling counterclockwise to q, we have pink or blue. Points are pink or green along the x axis approaching q. then pink or red until we are at a point z 180 ° from y. This pattern recurs on the outside of c on the right, except for r; points approaching r from the right are green blue or red. Red and blue both approach q and r from outside, else we could thicken the tips of the needles into normal regions.

Reflect if need be, so that the yellor orange border does not curve up. Now points approaching y from p are pink or blue. y is a transition point but not a choke point.

A pink red band runs outside of c, starting at r and moving counterclockwise to y, for more than 60 °, and thickening applies. A pink blue band runs inside from slightly before y to q. Suppose one band has pink at y but the other does not. The other band has pink starting 60 ° from y (outside), or slightly less then 60 ° from y (inside). Either way we have pink points 1 unit apart.

Suppose both bands have pink at y. The two pink ends taken together span at least 60 °. More than 60 ° is 1 color trouble. If 60 °, place points on c on either end of pink. Raise these points slightly. Since pink curves to the right at the right, leaning down towards red, the right point is in a pink region. Pivot the left point along a circle centered at the right point, and it crashes into pink. Thus even 60 ° is trouble. The same thing happens at z. Thus the pink ends are at q and r.

From r to q it's pink t °, red 60, blue 60, and pink t-60. The first two are outside and the next two are inside, with y as a transition point. t is the angle of yellow at p, - 60. t is strictly between 0 and 60, and 60-t is strictly between 0 and 60. The blue band on the outside of c is within 60 of q. However, blue approaches q on the left, else we could thicken the blue needle. This puts blue regions 1 unit apart, and is a contradiction.

If red and blue needles point at each other, there is one color on one side and one color on the other. We saw this earlier when two red needles point at each other. Put green on the left and yellow on the right. Green cannot descend down from q, even if it curves right, for it collides witht the green that rises straight up from p. Nor can green head straight up from q. If green approaches q from the right it comes to a point. The normal region below and to the right of q cannot be green red blue or yellow. That leaves pink or orange below q, and pink or orange above q. If it is the same color if fills in, covering the right side of q. The same thing happens at r.

The outside band across the top half of c is red orange or pink. The inside band is blue orange or pink. place y and z on c, at 60 and 120 degrees respectively. Let d be the unit circle centered at q, so that z is on c and d. Let e be the unit circle centered at r, so that y is on c and e. There are 4 regions at z defined by c and d. We'll start with the region above z. There is a comparable region above y, and if each region is filled in with one color, it can't be the same color. In fact none of the regions around y can match the region above z, or the region below z.

Remember that pink or orange fills in all the way to c, approaching the vertical line at q. Let's put pink on top, thus a band above d is not pink. Points above z are orange or red, and points to the right of z are orange or blue.

Suppose red is above and to the left of z, on either side of d. Move along d just a hair to the left of z. You are in the midle of a red region. Wiggle this point about, and note that red cannot approach q. But it must, else we could thicken the red needle. In the same way, blue cannot be inside and outside of d to the right of z. Naturally these results apply to y as well.

Suppose orange approaches q from below. That keeps orange away from the inner band of d.

Remember that the region to the right of z is blue and/or orange. Suppose it is orange, at least along the top of d. Let the region below be pink. The regions above and below y are not pink or orange, at least on the right. We have red above and blue below. The region to the right of y is not orange or pink or red. This is impossible, thus the region below z is blue.

If the region above z is red, then the region to the left of z can't be red, or orange, thus is pink. Blue meets pink somewhere below d, and orange meets red somewhere above d. Looking below y, orange and blue cannot persist past a circle centered at z and passing through y. Pink is below y for at least the right half of the region. If there is a pink blue border at y, combine this with the pink blue border at z and find 2 color trouble. so there is a pink orange border. Now the region below r can't be pink or orange, and that is a contradiction. Therefore the region to the left of z and above d is a continuation of orange. Either pink or red is to the left of z. We don't have orange needles, since there are 2 colors below d, so orange fills in above d. Nothing around y is orange. We still have the right half of the area below y as pink. If red approaches z from the left, the left half of the area above y is pink. Fill in with pink all the way around y. Orange meets r above and below. Remember this result as we move on. Without red, pink is left of z, and we have a pink blue border somewhere below z. There is a pink blue border below y, and the same 2 color trouble as before. That takes care of orange to the right of z.

Put blue to the right of z, just above d. There is no blue below, or orange, so pink. Pink and blue extend no farther than a circle centered at z and passing through y. The right half of the region below y is orange. The right half of the region above z is red. This puts orange all the way up the right side of y. Orange can't run more than 180 °, so the left half of the region above y is red. The left half of the region above z is orange. We have an orange red border, and a red orange border, 1 unit apart, and that is 2 color trouble. Therefore blue does not approach z from the right.

Those are all the cases, and the only one that works has orange running up the left side of r. However, we could do the same thing at the bottom of c, and the only case that works has pink running up the left side of r. This is a contradiction, so we can't have pink and orange at q. It is one color up the right side of q, and one color up the left side of r.

Put pink up the right side of q, covering 180 degrees. Yellow does not approach r from the left, since pink or orange covers the left side of r. Try to repain the tip of the red needle yellow. We can do this, unless yellow approaches q from the left and descends straight down. It may curve left, but it starts out heading down from q. Try to repain the tip of the blue needle yellow. We can do this, unless yellow approaches q from the left and rises straight up. It may curve left, but it starts out heading up from q. You might think about yellow needles up and down at q, but that implies one color on one side and one color on the other. Both blue and red must approach q on the left, so this is impossible. That puts yellow all the way along the left side of q. It's yellow on one side and pink on the other, perhaps allowing for some vertical needles at q. Red and blue must approach q, else we could thicken the needles at p, thus these needles are red and blue. Now q is looking very much like p. By symmetry, r also looks like p.

Suppose we have pink at both q and r. There is no pink around z or y. It is orange or blue below y and z. A border on either side implies a border on the other, and 2 color trouble. Put blue below z and orange below y. There is no orange around z. It's blue below and to the right, and red above and to the left. Red can't approach q, and neither can blue, so this is impossible.

Put pink beside q and orange beside r. There is no pink around z. Put blue to the right of z just above d. There is no blue below so orange. We can't alternate between blue and orange, so orange fills the region below, and blue fills the region to the right. Orange can't bend around blue, so the right side of the region above z is red. Red fills the top region and orange fills the left region. The red orange border could coincide with d, or could be straight, or could curve upward, but it is tangent to d.

Assume blue runs below z and inside of d. That puts orange above d. It's blue below z and orange to the right of z. Orange can't bend around blue so it's red left of z and orange above. The red orange border is tangent to d, as it was in the last paragraph.

Finally we could have orange below and to the right of z inside and outside of d. If red runs inside of d then orange runs outside of d, and orange bends around red. So it's orange inside of d and orange fills the regions below and left of z. If there is any blue or red then it's blue right of z and red above z. Red orange border is tagent to d. Orange outside of d still runs tangen to d, straight or perhaps curving up.

Finally we could have orange all the way around z.

The tricolor cases don't work. Put red and blue below d, and orange above. Let l be a line through q at 30 ° to the x axis. Remember that we have red and blue needles pointing at q. If they are below l, they collide with red or blue on the inside of d. thus they are both above l. That's a red and blue needle side by side pointing down at q, and that is lopsided. Put red and blue above d, and find red and blue needles side by side below l, pointing up ad q, which is also lopsided. So it's all orange around z.

In summary, it's orange and green bracketing r, pink around y, orange around z, pink and yellow bracketing q, orange around the point opposite to y, and pink around the point opposite to z. This pattern propagates all the way along the x axis.

Suppose pink orange and red meet at a vertex v somewhere on the top have of c, but not at y or z. u is just a hair above p on the y axis, and pretends to be a vertex with blue yellow and green. These are 2 points within 2 of each other, and all 6 colors are represented. Let w be 1 unit away from u and v. w is not r, y, z, or q. An entire disk about w is not blue yellow or green. The circle that is centered at w, and passes through v, might not cut through all 3 colors, but if we move w about, it will. This is a contradiction.

The same reasoning shows we can't have a vertex on c with pink orange and blue. This time u is just below p on the y axis.

5 colors don't meet at v, only 4 are allowed. Suppose a color repeats, thus needles pointing at each other. That puts 1 color on one side and 1 color on the other. If 2 of the 3 colors are orange and pink then we can ignore one of the two needles and find 3 colors and v and invoke the previous paragraph. So we have red above and blue below and either pink or orange poking in along c.

With no repeats we could have 4 colors, and red must be entirely above and blue must be entirely below. Put red and blue adjacent, on the right, and pink and orange on the left. Put u just above p to try. If the circle passing through w runs along a border, pull u a little closer to p. Now the circle passes through 2 colors. If they are pink and red then push w to the left and we have pink orange and red and we're done. If they are pink and orange then pull w to the right and the circle cuts through all 4 colors and we are done. If they are red and blue then push w to the left and the circle cuts through all 4 colors and we are done. If orange and blue, than lower u through p and hope the circle continues to cut through orange and blue. At that point we could move w and the circle cuts through orange pink and blue. The corner case is when the circle through v coincides with a border, perhaps pink and blue, or orange and red, or both, exactly when u = p. If orange turns into red but blue remains blue we have the blue red case and we have dealt with that. If blue turns into pink but orange remains orange we have the orange pink case and we have dealt with that. Suppose both colors change as u passes through p. Put w on the other side of u and v. This is the orange blue case. Put u just below p and find the contradiction.

Next put red above pink. That puts orange above blue. Remember that pink could cross c, or orange could cross c. If the w centered circle passes through pink and red, or blue and orange, shift w and cut through all 4 colors. If pink and orange, push w left and cut through pink red and orange. For illustration, put v at the top of c, and u just above p, and w 30 ° above r. Suppose the red orange border is less then 30 ° from normal at c. The circle about w cuts through pink red and orange. This will also happen if the border is exactly 30 ° from normal but does not curve away from normal with curvature 1. Put w on the other side, above q, and find the same when the red pink border is less than 30 ° from normal. So red is at least 60 °. Put p below u and find that blue is at least 30 ° from normal on either side.

Let's march along from z to y clockwise. Remember we start with orange above and below. Suppose orange changes to pink below. It can't remain orange above or orange is more than 180 °. It can't switch to red or we have orange pink red. If it switches to red and then blue, a vertex with 4 regions around, orange and pink are together and that doesn't work. It could switch to pink, so pink above and below, but that is very much like orange above and below, so put this to the side and let's continue. We could switch to blue below. Again, we can't remain orange above, and pink above is 3 colors, so it must be red. Orange gives way to blue below and red above. Now assume orange changes on top but remains orange below.

If all the red needles are below the x axis, you might thing they would run into each other, and eventually they do. Let the right edge of the red needle at p curve right. It has a certain radius of curvature k, as though the border was a circle of radius k centered at k,0. k could be any real number ≥ 1. Move to the red needle pointing up at r. Its left edge has a radius of curvature ≤ k-1, as though the border was a circle of radius k-1 centered at k,0. That leaves a non red annulus between the two concentric circles centered at k,0. The right edge of the needle has an even smaller radius of curvature. Continue down the x axis until the radius of curvature is less than 1, that is to say, the curvature is greater than 1, and that is a contradiction. Somewhere we run into a blue needle. So assume, as we have before, that a red needle points up at p, and assume a blue needle points up at q. @@ That completes the case of green on the left and yellow on the right.

Further Reading

The Hadwiger Nelson problem.